题意：有一个数列定义如下：\(a_1 = a_2 = 1, a_n = a_{n-a_{n-1}} + a_{n-1-a_{n-2}} (n \geq 3) \)，求\(\sum_{i=1}^n{a_i}\)。（\( 1 \leq n \leq 10^{18}\)，多组数据，\(T \leq 10^5\)）

        题解：先打个表观察一下。数列从1开始如下：1 1 2 2 3 4 4 4 5 6 6 7 8 8 8 8 9 10 10 11 12 12 12 13 14 14 15 16 16 16 16 16 …

可以发现这么一件事情：除了1以外，每个数的出现次数等于它二进制下从低位开始数第一个1的位置。由此我们可以得到出现次数相等的数字排列起来是一个等差数列（考虑lowbit相等的数，相邻间隔为其lowbit乘2），二分出\(a_n\)是多少，然后计算即可，时间复杂度是\(O(\log^2{n})\)的。

        有\(O(\log{n})\)的解法，依然不考虑\(a_1\)（因为\(a_1\)不满足这个性质），利用每个数出现的次数所组成的序列来看：\[1\ 2\ 1\ 3\ 1\ 2\ 1\ 4\ 1\ 2\ 1\ 3\ 1\ 2\ 1\ 5\ 1\ 2\ 1\ 3\ 1\ 2\ 1\ 4\ 1\ 2\ 1\ 3\ 1\ 2\ 1\ 6\]

仔细观察会发现这是个分形（也许），刚开始序列中只有一个数为1，之后我每次将该序列复制一遍，然后把最后一个数加1。

        第一次：\(1\ 2\)

        第二次：\(1\ 2\ 1\ 3\)

        第三次：\(1\ 2\ 1\ 3\ 1\ 2\ 1\ 4\)

        第四次：\(1\ 2\ 1\ 3\ 1\ 2\ 1\ 4\ 1\ 2\ 1\ 3\ 1\ 2\ 1\ 5\)

        利用该性质，可以通过预处理出数字为\(1..2^n\)时所有数出现次数的总数以及和。由于将任意一个该序列分为两半，前后两半只有最后一位是不一样的，所以可以通过类似快速幂的方法求出答案，处理到最后多出的数字一定是相等的（具体看代码）。

#include <bits/stdc++.h>
using namespace std;
const int mo=1e9+7;
long long Pow(long long x,int p)
{
	long long res=1;
	while (p)
	{
		if (p&1) (res*=x)%=mo;
		(x*=x)%=mo;
		p>>=1;
	}
	return res;
}
long long Mul(long long a,long long b)
{
	return (a%mo)*(b%mo)%mo;
}
long long c[64];
long long sum[64];
long long n;
long long Solve(long long x)
{
	long long ans=1,num=0;
	x--;
	for (int i=62;i>=0;i--) if (x>=c[i])
	{
		x-=c[i];
		ans=(ans+sum[i]+Mul(c[i],num))%mo;
		num+=(1ll<<i);
	}
	(ans+=Mul(x,num+1))%=mo;
	return ans;
}
int main()
{
	c[0]=1;c[1]=3;
	sum[0]=1;sum[1]=5;
	for (int i=2;i<63;i++) c[i]=c[i-1]*2+1,sum[i]=(2*sum[i-1]+Pow(2,i)+Pow(2,i-1)*(Pow(2,i)-1))%mo;
	int T;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%lld",&n);
		printf("%lld\n",Solve(n));
	}
	return 0;
}