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