「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 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