签到
题目背景
题解: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$。
输出格式
对于每行数据,输出答案。
输入输出样例
输入样例 #1
3
10
100
1000
输出样例 #1
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}$。