P5177 Check-in.

Solution: https://blog.csdn.net/kkkksc03/article/details/85008142

Compute $\sum_{i=1}^n \sum_{j=1}^n i \ xor \ j \in [\min(i,j),\max(i,j)]$. Since the answer may be very large, output the value modulo $10^9+7$.

The first line contains an integer $T$, the number of test cases. The next $T$ lines each contain one integer $n$.

For each test case, output the answer.

Explanation for the first sample: There are $20$ pairs $(i,j)$ that satisfy the condition. ``` i=1 j=3 i^j=2 i=1 j=5 i^j=4 i=1 j=7 i^j=6 i=1 j=9 i^j=8 i=2 j=6 i^j=4 i=2 j=7 i^j=5 i=2 j=10 i^j=8 i=3 j=1 i^j=2 i=3 j=6 i^j=5 i=3 j=7 i^j=4 i=3 j=10 i^j=9 i=5 j=1 i^j=4 i=6 j=2 i^j=4 i=6 j=3 i^j=5 i=7 j=1 i^j=6 i=7 j=2 i^j=5 i=7 j=3 i^j=4 i=9 j=1 i^j=8 i=10 j=2 i^j=8 i=10 j=3 i^j=9 ``` Constraints: For $27\%$ of the testdata, $T\le 5$, $n \le 1000$. For $54\%$ of the testdata, $T\le 20$, $n \le 5 \times 10^5$. For $90\%$ of the testdata, $T\le 10^5$, $n \le 10^{18}$. For the last test point, $T=3\times 10^6 \ ,\ n\le 10^{18}$. Translated by ChatGPT 5