G. Sum the Fibonacci
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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
  • (sa | sb) & sc & (sd ^ se) = 2i for some integer i
  • sa & sb = 0

Here, '|' is the bitwise OR, '&' is the bitwise AND and '^' is the bitwise XOR operation.

Find the sum of f(sa|sb) * f(sc) * f(sd^se) 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 109 + 7.

Input

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

The second line of input contains n integers si (0 ≤ si < 217).

Output

Output the sum as described above, modulo 109 + 7

Examples
Input
2
1 2
Output
32
Input
3
7 4 1
Output
3520
Input
10
1 3 0 7 3 7 6 5 7 5
Output
1235424
Input
10
50 9 11 44 39 40 5 39 23 7
Output
113860062