CF449D.Jzzhu and Numbers

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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
```
0
```
输入#2
```
4
0 1 2 3
```
输出#2
```
10
```
输入#3
```
6
5 2 0 5 2 1
```
输出#3
```
53
```

首页