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 2\,000~

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 \min_2(s) \oplus \max_2(s) = v~

Where ~s_{\ge 2}~ represents a subsequence of ~a~ containing at least two elements, ~\min_2~ is the second minimum, ~\oplus~ is the bitwise xor operator, ~\max_2~ 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{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~.