CF449D.Jzzhu and Numbers

Jzzhu have n non-negative integers _a_1, _a_2, ..., a__n. We will call a sequence of indexes _i_1, _i_2, ..., i__k (1 ≤ _i_1 < _i_2 < ... < i__k ≤ n) a group of size k.

Jzzhu wonders, how many groups exists such that _a__i_1 & _a__i_2 & ... & a__i__k = 0 (1 ≤ k ≤ n)? Help him and print this number modulo 1000000007 (109 + 7). Operation x & y denotes bitwise AND operation of two numbers.

Jzzhu 有 $n$ 个非负整数 $a_1, a_2, \dots, a_n$。我们将满足 $1 \le i_1 < i_2 < \dots < i_k \le n$ 的下标序列 $i_1, i_2, \dots, i_k$ 称为一个大小为 $k$ 的组。

Jzzhu 想知道：满足 $a_{i_1} \& a_{i_2} \& \dots \& a_{i_k} = 0$（其中 $1 \le k \le n$）的组共有多少个？请你帮他计算，并将结果对 $1000000007$（即 $10^9 + 7$）取模后输出。运算符 $x \& y$ 表示两个数的按位与（bitwise AND）运算。

The first line contains a single integer n (1 ≤ n ≤ 106). The second line contains n integers _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 106).

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$）。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq 10^6$）。

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

输出一个整数，表示所需组数对 1000000007（即 $10^9 + 7$）取模的结果。