Sum the Fibonacci

4000ms

262144K

Description:

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ⁱ 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⁹ + 7.

Input:

The first line of input contains an integer n (1 ≤ n ≤ 10⁶).

The second line of input contains n integers s_i (0 ≤ s_i < 2¹⁷).

Output:

Output the sum as described above, modulo 10⁹ + 7

Sample Input:

2
1 2

Sample Output:

Sample Input:

3
7 4 1

Sample Output:

Sample Input:

10
1 3 0 7 3 7 6 5 7 5

Sample Output:

Sample Input:

10
50 9 11 44 39 40 5 39 23 7

Sample Output:

113860062

Informação

Provedor Codeforces

Código CF914G