← 返回题目

题库练习 Jzzhu and Numbers

← 上一题下一题 →

A9485 | $Jzzhu and Numbers$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

Jzzhu have $n$ non-negative integers $a_{1},a_{2},...,a_{n}$ . We will call a sequence of indexes $i_{1},i_{2},...,i_{k}$ $(1<=i_{1}<i_{2}<...<i_{k}<=n)$ a group of size $k$ . Jzzhu wonders, how many groups exists such that $a_{i1}$ & $a_{i2}$ & ... & $a_{ik}=0$ $(1<=k<=n)$ ? Help him and print this number modulo $1000000007$ $(10^{9}+7)$ . Operation $x$ & $y$ denotes bitwise AND operation of two numbers.

输入格式

The first line contains a single integer $n$ $(1<=n<=10^{6})$ . The second line contains $n$ integers $a_{1},a_{2},...,a_{n}$ $(0<=a_{i}<=10^{6})$ .

输出格式

Output a single integer representing the number of required groups modulo $1000000007$ $(10^{9}+7)$ .

输入输出样例

输入 #1

3
2 3 3

输出 #1

输入 #2

4
0 1 2 3

输出 #2

输入 #3

6
5 2 0 5 2 1

输出 #3

C++ 编辑器

输入

输出