Description
Chiaki is interested in an infinite sequence \(a_1,a_2,a_3,...\) which is defined as follows:

\[a_n=\begin{cases} 1 &,n=1,2\\a_{n−a_{n−1}}+a_{n−1−a_{n−2}}&,n\geqslant3\end{cases} \]

Chiaki would like to know the sum of the first \(n\) terms of the sequence, i.e. \(\sum\limits_{i=1}^na_i\). As this number may be very large, Chiaki is only interested in its remainder modulo \((10^9+7)\).

Input
There are multiple test cases. The first line of input contains an integer \(T (1\leqslant T\leqslant 10^5)\), indicating the number of test cases. For each test case:
The first line contains an integer \(n (1\leqslant n\leqslant 10^{18})\).

Output
For each test case, output an integer denoting the answer.

Sample Input

10
1
2
3
4
5
6
7
8
9
10

Sample Output

1
2
4
6
9
13
17
21
26
32

---

遇到看不懂的数列，首先就应该根据它的构造方法打表找规律

通过打表可得数列前几项为1,1,2,2,3,4,4,4,5,6,6,7,8,8,8,8,...容易发现，在除去最开始的1后，记\(c_i\)为\(i\)出现的次数，则有\(c_{2k}=c_k+1,c_{2k+1}=1\)

我们记\(s_k=\sum\limits_{i=1}^kc_i\)，则有

\(s_{2k}=(c_1+c_3+....+c_{2k-1})+(c_2+c_4+...+c_{2k})=s_k+2k\)

\(s_{2k+1}=s_{2k}+c_{2k+1}=s_k+2k+1\)

故可得\(s_n\)的递推式\(s_n=s_{\lfloor\frac{n}{2}\rfloor}+n\)，此时\(s_n\)表示1~n在序列中总共出现的次数

题目要求\(S=\sum\limits_{i=1}^na_i\)，我们结合打表的数据，对其进行分组可得\(S=\sum\limits_{i=1}^n{i}+\sum\limits_{i=1}^{\lfloor\frac{n}{2}\rfloor}2\times i+\sum\limits_{i=1}^{\lfloor\frac{n}{2^2}\rfloor}2^2\times i+...=\sum\limits_{j=0}\sum\limits_{i=1}^{\lfloor\frac{n}{2^j}\rfloor}2^j\times i\)

故我们可用二分，通过\(s_n\)找到一个合适的\(n\)，再根据上式计算\(S\)，最后再加上一些多出来的部分即可

并且，根据打表得出的规律，我们可以发现\(n\)基本在\(\frac{N}{2}\)附近波动（\(N\)为读入），故可以缩小二分的范围

/*program from Wolfycz*/
#include<map>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define Fi first
#define Se second
#define ll_inf 1e18
#define MK make_pair
#define sqr(x) ((x)*(x))
#define pii pair<int,int>
#define int_inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>inline T frd(T x){
	int f=1; char ch=gc();
	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')    f=-1;
	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<1)+(x<<3)+ch-'0';
	return x*f;
}
template<typename T>inline T read(T x){
	int f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';
	return x*f;
}
inline void print(int x){
	if (x<0)	putchar('-'),x=-x;
	if (x>9)	print(x/10);
	putchar(x%10+'0');
}
const int P=1e9+7,Inv=5e8+4;
ll Cnt(ll x){return !x?0:Cnt(x>>1)+x;}
ll Binary_Search(ll l,ll r,ll m){
	while (l<=r){
		ll mid=(l+r)>>1;
		if (Cnt(mid)>m)	r=mid-1;
		else	l=mid+1;
	}
	return l-1;
}
int main(){
	int T=read(0);
	while (T--){
		int Ans=1;
		ll m=read(0ll)-1,n=Binary_Search((m>>1)-100,(m>>1)+100,m);
		for (int i=0;1ll<<i<=n;i++){
			ll delta=1ll<<i,E=n/delta*delta;
			Ans=(Ans+1ll*(E%P)*((E/delta+1)%P)*Inv%P)%P;
		}
		Ans=(Ans+1ll*(m-Cnt(n))%P*((n+1)%P)%P)%P;
		printf("%d\n",Ans);
	}
	return 0;
}