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_i1 & a_i2 & ... & a_ik = 0(1 ≤ k ≤ n)? Help him and print this number modulo 1000000007(10⁹ + 7). Operation x & y denotes bitwise AND operation of two numbers.

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 a single integer representing the number of required groups modulo 1000000007(10⁹ + 7).