← 返回题目列表

Codeforces · 449/D

D. Jzzhu 和数字

中文机器翻译题面 查看原题

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 运算表示两个数字的按位与运算。

输入

第一行包含一个整数 n (1 ≤ n ≤ 106)。第二行包含 n 个整数 a1, a2, ..., an (0 ≤ ai ≤ 106)。

输出

输出一个整数,表示所需组数以 1000000007 (109 + 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