Sibi-Xor
By Francisco Elio Parente Arcos Filho, UEA 
Brazil
By Francisco Elio Parente Arcos Filho, UEA Brazil
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.
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.
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 |
3 |
|
4 |
57 |
|
5 |
219 |