Background

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

Problem Description

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$.

Input Format

The first line contains an integer $T$, the number of test cases.

The next $T$ lines each contain one integer $n$.

Output Format

For each test case, output the answer.

3
10
100
1000

20
2634
325502

Hint

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