签到

题目背景

题解: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}$。