2973: CF449 - D. Jzzhu and Numbers
[Creator : ]
Description
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 thata $i_1\& a_i2\& ... \& a_{i_k}=0\ (1≤k≤n)$? Help him and print this number modulo $10^9+7$. Operation $x\& y$ denotes bitwise AND operation of two numbers.
Jzzhu wonders, how many groups exists such thata $i_1\& a_i2\& ... \& a_{i_k}=0\ (1≤k≤n)$? Help him and print this number modulo $10^9+7$. Operation $x\& y$ denotes bitwise AND operation of two numbers.
Input
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)$.
The second line contains $n$ integers $a_1,a_2,...,a_n\ (0≤a_i≤10^6)$.
Output
Output a single integer representing the number of required groups modulo $10^9+7$.
Sample 1 Input
3
2 3 3
Sample 1 Output
0
Sample 2 Input
4
0 1 2 3
Sample 2 Output
10
Sample 3 Input
6
5 2 0 5 2 1
Sample 3 Output
53