You are given an array $*s*$ of $*n*$ non-negative integers.

A 5-tuple of integers $(*a*, *b*, *c*, *d*, *e*)$ is said to be valid if it satisfies the following conditions:

• $1 ≤ *a*, *b*, *c*, *d*, *e* ≤ *n*$
• $(*s*_{*a*}$ | $*s*_{*b*})$ & $*s*_{*c*}$ & $(*s*_{*d*}$ ^ $*s*_{*e*}) = 2^{*i*}$ for some integer $*i*$
• $*s*_{*a*}$ & $*s*_{*b*} = 0$

Here, '|' is the bitwise OR, '&' is the bitwise AND and '^' is the bitwise XOR operation.

Find the sum of $*f*(*s*_{*a*}$|$*s*_{*b*}) * *f*(*s*_{*c*}) * *f*(*s*_{*d*}$^$*s*_{*e*})$ over all valid 5-tuples $(*a*, *b*, *c*, *d*, *e*)$, where $*f*(*i*)$ is the $*i*$-th Fibonnaci number ($*f*(0) = 0, *f*(1) = 1, *f*(*i*) = *f*(*i* - 1) + *f*(*i* - 2)$).

Since answer can be is huge output it modulo $10^{9} + 7$.

Input

The first line of input contains an integer $*n*$ ($1 ≤ *n* ≤ 10^{6}$).

The second line of input contains $*n*$ integers $*s*_{*i*}$ ($0 ≤ *s*_{*i*} < 2^{17}$).

Output

Output the sum as described above, modulo $10^{9} + 7$