Sum the Fibonacci

题意翻译

给你一个长度为$n$ 的数组$s$ .定义五元组$(a,b,c,d,e)$ 是合法的当且仅当: 1. $1\le a,b,c,d,e\le n$ 2. $(s_a|s_b)\&s_c\&(s_d$ ^$s_e)=2^i,i\in Z$ 3. $s_a\&s_b=0$ 对于所有合法的五元组$(a,b,c,d,e)$ 求$\sum f(s_a|s_b)*f(s_c)*f(s_d$ ^$s_e)\mod 10^9+7$ $f_0=0,f_1=1,f_i=f_{i-1}+f_{i-2}$ $1\le n\le10^6,0\le s_i\lt2^{17}$ Translated by @Kelin

题目描述

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 $

输入输出样例

输入样例 #1

2
1 2

输出样例 #1

32

输入样例 #2

3
7 4 1

输出样例 #2

3520

输入样例 #3

10
1 3 0 7 3 7 6 5 7 5

输出样例 #3

1235424

输入样例 #4

10
50 9 11 44 39 40 5 39 23 7

输出样例 #4

113860062

题意翻译

给你一个长度为$n$ 的数组$s$ .定义五元组$(a,b,c,d,e)$ 是合法的当且仅当: 1. $1\le a,b,c,d,e\le n$ 2. $(s_a|s_b)\&s_c\&(s_d$ ^$s_e)=2^i,i\in Z$ 3. $s_a\&s_b=0$ 对于所有合法的五元组$(a,b,c,d,e)$ 求$\sum f(s_a|s_b)*f(s_c)*f(s_d$ ^$s_e)\mod 10^9+7$ $f_0=0,f_1=1,f_i=f_{i-1}+f_{i-2}$ $1\le n\le10^6,0\le s_i\lt2^{17}$ Translated by @Kelin