Tổng XOR Của Mọi Cặp

Cho $N$ số nguyên không âm $A_1,A_2,\dots ,A_N$. Hãy tính

và in phần dư khi chia cho $1000000007$.

Input

• Dòng đầu chứa số nguyên $N$.
• Dòng tiếp theo chứa $N$ số nguyên $A_1,A_2,\dots ,A_N$.

Output

• In tổng yêu cầu theo modulo $1000000007$.

Constraints

• $2\le N\le 3\cdot 10^5$.
• $0\le A_i<2^{60}$.

Scoring

• Subtask $1$ ($50$ điểm): $10$ test có $N$ nhỏ, cho phép duyệt mọi cặp.
• Subtask $2$ ($50$ điểm): $10$ test đầy đủ; test $19$ và $20$ đều có $N=3\cdot 10^5$, một test nhấn mạnh bit cao và một test phân bố ngẫu nhiên.

Example

3
0 1 4

10