Migrated from Lutece 1294 天行廖的游戏

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

天行健，君子以自强不息。地势坤，廖爷以厚德载物

一日在喵哈哈村，天行廖和沈宝宝正在玩一个游戏。

天行廖分别在$N$个纸片上写上一个数字，并放到一个盒子中。

现在沈宝宝要从盒子中抓出任意张纸片。

如果沈宝宝抓出的纸片上的数字$A_{i1}$,$A_{i2}$,....$A_{ik}$满足$A_{i1}$ & $A_{i2}$ & ....$A_{ik} = 0$ ( $i_{1} < i_{2} … < i_{k}$)，那么天行廖赢得这次游戏的胜利，否则沈宝宝赢。

Input

第一行输入$1$个整数$N。$($1 \leq N \leq 10^6$)

第二行输入$N$个整数$A_1，A_2....A_N$。($1 \leq A_i \leq 10^6$)

Output

输出获胜的方案数量。因为结果可能很大，输出答案对$10^9+7$取模的结果即可。

Samples

3
2 3 3

0

4
0 1 2 3

10

6
5 2 0 5 2 1

53

2
0 0

3

Note

对于第$4$组样例，三组合法的解是$( A_1 ) , ( A_2 ) , ( A_1,A_2 )$

Resources

每周一题 Div1