「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (大一组)
F. &
单点时限: 2.0 sec
内存限制: 256 MB
& 同学最近很生气，因为他没有拿到校赛一等奖。
一气之下他决定把室友 & 了。他有 $n$ 个室友，从 $1$ 到 $n$ 编号，第 $i$ $(1 \leq i \leq n)$ 个室友有一个生命值 $a_i$。如果能选出一组 $t_1, t_2, \ldots, t_k$ $(1 \leq t_1 < t_2 < \ldots < t_k \leq n)$ 使得 $a_{t_1}$ & $a_{t_2}$ & $\cdots$ & $a_{t_k} = 0$ $(1 \leq k \leq n)$，他就会很开心。
他能选出多少不同组的室友呢？由于答案很大，请输出答案对 $10^9+7$ 取模之后的结果。
输入格式
输出包含多个测试文件，每个测试文件只有单个测试点。
第一行一个整数 $n$。第二行是用空格隔开的 $n$ 个整数 $a_1, a_2, \ldots, a_n$。
总共有 $10$ 个测试点。其中：
- 测试点 $1,2$ 满足：$1 \leq n \leq 10, 0 \leq a_i \leq 10^6$；
- 测试点 $3,4,5$ 满足：$1 \leq n \leq 1~000, 0 \leq a_i \leq 10~000$。
- 测试点 $6,7,8,9,10$ 满足：$1 \leq n \leq 10^6, 0 \leq a_i \leq 10^6$。
输出格式
输出一个整数表示答案。
样例
Input
4 3 2 1 0
Output
10
Input
6 5 2 0 5 2 1
Output
53
通知
比赛状态发生变化，点 OK 刷新。
通知