#P13981. CF449D Jzzhu and Numbers

CF449D Jzzhu and Numbers

题目描述

Jzzhu 有 nn 个非负整数 a1,a2,⋯ ,ana_{1},a_{2},\cdots,a_{n}。我们将一组下标序列 i1,i2,⋯ ,iki_{1},i_{2},\cdots,i_{k}(1≤i1<i2<⋯<ik≤n1 \le i_{1}<i_{2}< \cdots <i_{k} \le n)称为大小为 kk 的一组“组”。

Jzzhu 想知道,有多少组满足 $a_{i_1} \operatorname{\&} a_{i_2} \operatorname{\&} \cdots \operatorname{\&} a_{i_k}=0$(1≤k≤n1 \le k \le n)?请帮他计算,并输出满足条件的组数对 10000000071000000007(109+710^{9}+7)取模后的结果。操作 x&⁡yx \operatorname{\&} y 表示两个数的按位与运算。

输入格式

第一行包含一个整数 nn(1≤n≤1061\le n\le 10^{6})。
第二行包含 nn 个整数 a1,a2,⋯ ,ana_{1},a_{2},\cdots,a_{n}(0≤ai≤1060\le a_{i}\le 10^{6})。

输出格式

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

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

说明/提示

由 ChatGPT 5 翻译