Sum the Fibonacci

给定长度为 $n$ 的数组 $s$。定义五元组 $(a,b,c,d,e)$ 是**好的**当且仅当: 1. $1\le a,b,c,d,e\le n$； 2. $\exists i\in \mathbb{Z}_+$，使得 $(s_a\operatorname{or}s_b)\operatorname{and}s_c\operatorname{and}(s_d \operatorname{xor} s_e)=2^i$； 3. $s_a\operatorname{and}s_b=0$。 对于所有**好的**五元组 $(a,b,c,d,e)$，求出 $f(s_a\operatorname{or}s_b)\times f(s_c)\times f(s_d \operatorname{xor} s_e)$ 的和。对 $(10^9+7)$ 取模。 其中 $f$ 为 Fibonacci 数列，满足 $f_0=0,f_1=1,f_i=f_{i-1}+f_{i-2}$。$\mathrm{and},\mathrm{or},\mathrm{xor}$ 分别代表按位与，按位或，按位异或运算。 $1\le n \le 10^6$，$0\le s_i \lt 2^{17}$。 Statement fixed by Starrykiller

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 $

2
1 2

32

3
7 4 1

3520

10
1 3 0 7 3 7 6 5 7 5

1235424

10
50 9 11 44 39 40 5 39 23 7

113860062