rt。

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T> void read(T &x){
	x = 0;
	T f = 1;char ch = getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		{
			f = -1,ch = getchar();
			break;
		}
		ch = getchar();
	}
	while(ch>='0'&&ch<='9')
		x = ((x<<3)+(x<<1)+ch-48)%329616,ch = getchar();
	x*=f;
}
struct juzhen {
	public:
		int a[2][2];
};
juzhen p;
int mod;
juzhen juzhenchengfa(juzhen x,juzhen y) { //It is zhouly
	juzhen res;
	memset(res.a,0,sizeof(res.a));
	for(register int i=0; i<2; i++)
		for(register int j=0; j<2; j++)
			for(register int k=0; k<2; k++)
				res.a[i][j]=(res.a[i][j]+(x.a[i][k]*y.a[k][j])%mod)%mod;
	return res;
}
juzhen juzhenkuaisumi(juzhen x,int y) {
	juzhen res;
	res.a[0][0]=-1;
	while(y>0) {
		if(y&1) {
			if(res.a[0][0]==-1)res=x;
			else res=juzhenchengfa(res,x);
		}
		x=juzhenchengfa(x,x);
		y>>=1;
	}
	return res;
}
int t,k;
signed main() {
	p.a[0][0]=1,p.a[0][1]=1,p.a[1][0]=1,p.a[1][1]=0;
	cin>>t;
	while(t--) {
		read(k);
		mod=2000000016;
		if(k==0){
			cout<<"0\n";
			continue;
		}
		if(k<=2){
		    cout<<"1\n";
			continue;
		}
		juzhen q=juzhenkuaisumi(p,k-2);
		int ans=q.a[0][1]+q.a[0][0];
		k=ans%mod;
		mod=1000000007;
		q=juzhenkuaisumi(p,k-2);
		ans=q.a[0][1]+q.a[0][0];
		cout<<ans<<"\n";
	}
}