У Jzzhu есть n неотрицательных целых чисел a1, a2, ..., an. Назовем последовательность индексов i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n) группой размера k.
Jzzhu интересно, сколько существует таких групп, что ai1 & ai2 & ... & aik = 0 (1 ≤ k ≤ n)? Помогите ему найти их количество по модулю 1000000007 (109 + 7).
Операция x & y обозначает операцию побитового И двух чисел.
Выходные данные
Выведите единственное целое число — количество требуемых групп по модулю 1000000007 (109 + 7).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 3 3
|
0
|
|
2
|
4
0 1 2 3
|
10
|
|
3
|
6
5 2 0 5 2 1
|
53
|