3273. &

单点时限: 2.0 sec

内存限制: 256 MB

& 同学最近很生气,因为他没有拿到校赛一等奖。

一气之下他决定把室友 & 了。他有 n 个室友,从 1n 编号,第 i (1in) 个室友有一个生命值 ai。如果能选出一组 t1,t2,,tk (1t1<t2<<tkn) 使得 at1 & at2 & & atk=0 (1kn),他就会很开心。

他能选出多少不同组的室友呢?由于答案很大,请输出答案对 109+7 取模之后的结果。

输入格式

输出包含多个测试文件,每个测试文件只有单个测试点。

第一行一个整数 n。第二行是用空格隔开的 n 个整数 a1,a2,,an

总共有 10 个测试点。其中:

  • 测试点 1,2 满足:1n10,0ai106
  • 测试点 3,4,5 满足:1n1 000,0ai10 000
  • 测试点 6,7,8,9,10 满足:1n106,0ai106

输出格式

输出一个整数表示答案。

样例

Input
4
3 2 1 0
Output
10
Input
6
5 2 0 5 2 1
Output
53

9 人解决,21 人已尝试。

19 份提交通过,共有 92 份提交。

7.3 EMB 奖励。

创建: 7 年,10 月前.

修改: 7 年,7 月前.

最后提交: 2 周,2 天前.

来源: 2017 华东师范大学校赛

题目标签