Jzzhu and Numbers

题意翻译

给出一个长度为n的序列$a_1,a_2...a_n$。求构造出一个序列$i_1 < i_2 < ... < i_k(1\le{k}\le{n})$使得$a_{i_1}\&a_{i_2}\&...\&a_{i_k}=0$ 。求方案数模$10^9+7$ 。 也就是从$\{a_i\}$ 里面选出一个非空子集使这些数按位与起来为0. 感谢@租酥雨 提供的翻译

题目描述

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_{i1} $ & $ a_{i2} $ & ... & $ a_{ik}=0 $ $ (1<=k<=n) $ ? Help him and print this number modulo $ 1000000007 $ $ (10^{9}+7) $ . Operation $ x $ & $ y $ denotes bitwise AND operation of two numbers.

输入输出格式

输入格式

The first line contains a single integer $ n $ $ (1<=n<=10^{6}) $ . The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ $ (0<=a_{i}<=10^{6}) $ .

输出格式

Output a single integer representing the number of required groups modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

3
2 3 3

输出样例 #1

0

输入样例 #2

4
0 1 2 3

输出样例 #2

10

输入样例 #3

6
5 2 0 5 2 1

输出样例 #3

53