Migrated from Lutece 1054 Hug the princess again

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is an array with $n$ elements. Now Alice is wondering the result of the following expression.

$\displaystyle{\sum_{1 \leq i < j \leq n} (a_i \wedge a_j) \times (a_i \& a_j)}$

As is known to everyone of you, Bob loves Alice very much. Could you tell Bob the answer to help Bob leave a good impression on Alice?

Input

The first line contains an integer $n$, indicating the size of the array.

The next line contains $n$ integers $a_i$, indicating the elements of the array.

It is guaranteed that $1 \leq n \leq 1000000, 0 \leq a_i \leq 1000000$.

Output

Print the answer module $1000000007$ in one line.

Samples

4
0 1 2 3

4

Resources

The 13th UESTC Programming Contest Final