URI Online Judge | 2811

Sibi-Xor

By Francisco Elio Parente Arcos Filho, UEA BR Brazil

Timelimit: 1

Dabriel went to visit his friend Farcos in his hometown, Manaus, in the state of Amazonas. When he got there, Dabriel was surprised at the way people spoke because of the very specific regional expressions they used. One curious expression he heard from a Farcos talk with his other friend RapBoy was "Sibicho", which is a reduction of the phrase "Look at that bug, O". A well-used regionalism to show disdain for what one hears or doubts one's assertion

The first time he heard the expression Dabriel thought it was the bitwise operation on numbers called Sibi-Xor that he had learned recently at the university and explained to Farcos. Farcos, in turn, was very happy to discover the operation because, in addition to enjoying bitwise operations, he found a way to make Rapboy stop using that expression with him in a tone of disdain. Now every time Rapboy said "Sibicho" he would have to tell Farcos the Sibi-Xor Result from a list of Numbers provided by him.

The Sibi-Xor operation on a list of numbers consists of 3 steps:

1)Make the AND-bitwise of all subsequences in the list. We will call each result subset-and.

2)Do the XOR-bitwise of all subset-and's that were formed with the same amount of elements.

3)Add up all the results from step 2.

For example, for the list A = {14, 15, 35, 7} provided by Farcos, Rapboy must answer the

Sibi-Xor(A) =

(14 ^ 15 ^ 35 ^ 7) +

((15 & 35) ^ (14 & 35) ^ (15 & 7) ^ (35 & 7) ^ (14 & 7) ^ (14 & 15)) +

((15 & 35 & 7) ^ (14 & 35 & 7) ^ (14 & 15 & 7) ^ (14 & 15 & 35)) +

(14 & 15 & 35 & 7)

= 57

Where '&' symbolizes the and-bitwise operation and '^' the xor-bitwise operation.

Input

The first line of the entry contains a N integer (1 ≤ N ≤ 2000) representing the number of numbers in the Farcos list. The second line contains N integers Ai (0 ≤ Ai < 264) corresponding to lists of Farcos numbers.

Output

The output consists of a single line containing Rapboy's response, that is, the sibi-xor of the numbers provided by Farcos. Since the response can be a very large number, print only your module for 109+7.

Input Samples Output Samples

3
1 2 3

3

4
14 15 35 7

57

5
6 42 105 63 20

219