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.

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 the sum as described above, modulo 10⁹ + 7