You are given an array of $N$ positive integers, $a_1,a_2,\dots a_N$. Let the value of a collection of at least two numbers be the bitwise xor of its second minimum and second maximum. Determine the sum of the values of all subsequences of $a$ which contain at least two elements. Since this value may be huge, output it modulo ${10}^9+7$.

Constraints

$1\le N\le 2\times {10}^5$
$0\le a_i<2^{30}$

Subtask 1 [20%]

$1\le N\le 2000$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains one integer, $N$, the length of the array.

The next line contains $N$ space-separated integers, $a_1,a_2,\dots ,a_N$, the array of positive integers.

Output Specification

Output one line containing one integer, the sum of the values of all subsequences which contain at least two elements, modulo ${10}^9+7$.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

64

Explanation for Sample 1

The following are the values of every subsequence containing at least two elements:

Format:
$s_{\ge 2}\to \underset{2}{min}(s)\oplus \underset{2}{max}(s)=v$

Where $s_{\ge 2}$ represents a subsequence of $a$ containing at least two elements, $\underset{2}{min}$ is the second minimum, $\oplus$ is the bitwise xor operator, $\underset{2}{max}$ is the second maximum, and $v$ is the resulting value of $s_{\ge 2}$.

$[3,1]\to 3\oplus 1=2$
$[3,4]\to 4\oplus 3=7$
$[3,1]\to 3\oplus 1=2$
$[3,5]\to 5\oplus 3=6$

$[1,4]\to 4\oplus 1=5$
$[1,1]\to 1\oplus 1=0$
$[1,5]\to 5\oplus 1=4$

$[4,1]\to 4\oplus 1=5$
$[4,5]\to 5\oplus 4=1$

$[1,5]\to 5\oplus 1=4$

Subsequences with $3$ elements are omitted since they all have a value of $0$.

$[3,1,4,1]\to 1\oplus 3=2$
$[3,1,4,5]\to 3\oplus 4=7$
$[3,1,1,5]\to 1\oplus 3=2$
$[3,4,1,5]\to 3\oplus 4=7$
$[1,4,1,5]\to 1\oplus 4=5$

$[3,1,4,1,5]\to 1\oplus 4=5$

Total value of all subsequences with at least two elements: $2+7+2+6+5+0+4+5+1+4+2+7+2+7+5+5=\boxed{{\displaystyle 64}}$

Sample Input 2

10
5 1 29 8 7 10 48 15 33 59

Sample Output 2

30210

Sample Input 3

50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 1000000000 1000000000

Sample Output 3

119486481

Explanation for Sample 3

Remember to output the answer modulo ${10}^9+7$.