题目描述

Jzzhu 有 $n$ 个非负整数 $a_{1},a_{2},\cdots,a_{n}$。我们将一组下标序列 $i_{1},i_{2},\cdots,i_{k}$（$1 \le i_{1}<i_{2}< \cdots <i_{k} \le n$）称为大小为 $k$ 的一组“组”。

Jzzhu 想知道，有多少组满足 $a_{i_1} \operatorname{\&} a_{i_2} \operatorname{\&} \cdots \operatorname{\&} a_{i_k}=0$（$1 \le k \le n$）？请帮他计算，并输出满足条件的组数对 $1000000007$（$10^{9}+7$）取模后的结果。操作 $x \operatorname{\&} y$ 表示两个数的按位与运算。

输入格式

第一行包含一个整数 $n$（$1\le n\le 10^{6}$）。
第二行包含 $n$ 个整数 $a_{1},a_{2},\cdots,a_{n}$（$0\le a_{i}\le 10^{6}$）。

输出格式

输出一个整数，表示满足条件的组数对 $1000000007$ 取模后的结果。

3
2 3 3

0

4
0 1 2 3

10

6
5 2 0 5 2 1

53

说明/提示

由 ChatGPT 5 翻译