Jzzhu and Numbers

2000ms

262144K

Description:

Jzzhu have n non-negative integers a₁, a₂, ..., a_n. We will call a sequence of indexes i₁, i₂, ..., i_k (1 ≤ i₁ < i₂ < ... < i_k ≤ n) a group of size k.

Jzzhu wonders, how many groups exists such that a_i₁ & a_i₂ & ... & a_{i_k} = 0 (1 ≤ k ≤ n)? Help him and print this number modulo 1000000007 (10⁹ + 7). Operation x & y denotes bitwise AND operation of two numbers.

Input:

The first line contains a single integer n (1 ≤ n ≤ 10⁶). The second line contains n integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁶).

Output:

Output a single integer representing the number of required groups modulo 1000000007 (10⁹ + 7).

Sample Input:

3
2 3 3

Sample Output:

Sample Input:

4
0 1 2 3

Sample Output:

Sample Input:

6
5 2 0 5 2 1

Sample Output:

Informação

Provedor Codeforces

Código CF449D