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*_{*i*_{1}}$ & $*a*_{*i*_{2}}$ & ... & $*a*_{*i*_{*k*}} = 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.

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})$.

Output

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