题目背景

题解：https://blog.csdn.net/kkkksc03/article/details/85008142

题目描述

求$\sum_{i=1}^n \sum_{j=1}^n i \ xor \ j \in [\min(i,j),\max(i,j)]$

由于答案可能过大，输出答案对$10^9+7$取模的值。

输入格式

第一行，一个整数$T$，为数据组数。

下面$T$行，每行一个整数$n$。

输出格式

对于每行数据，输出答案。

3
10
100
1000

20
2634
325502

提示

第一组样例解释：

符合题意的$(i,j)$有$20$对。

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

对于27%的数据，$T\le 5, n \le 1000$。

对于54%的数据，$T\le 20, n \le 5 \times 10^5$。

对于90%的数据，$T\le 10^5, n \le 10^{18}$。

最后一个点，$T=3\times 10^6 \ ,\ n\le 10^{18}$。