A11508 | Sum the Fibonacci

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

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 the sum as described above, modulo $10^{9}+7$