#include<bits/stdc++.h>
#define int long long
using namespace std;
int m=1000000007;
vector<vector<int> > mul(vector<vector<int> > a,vector<vector<int> > b){
	vector<vector<int> > c(a.size(),vector<int>(b[0].size()));
	for(int i=0;i<a.size();i++){
		for(int j=0;j<b[0].size();j++){
			for(int k=0;k<a[0].size();k++){
				c[i][j]+=a[i][k]*b[k][j];
				c[i][j]%=m;
			}
		}
	}
	return c;
}
vector<vector<int> > qp(vector<vector<int> > a,int n){
	vector<vector<int> > b(a[0].size(),vector<int>(a.size()));
	for(int i=0;i<b.size();i++){
		b[i][i]=1;
	}
	while(n){
		if(n%2)b=mul(a,b);
		a=mul(a,a);
		n/=2;
	}
	return b;
}
signed main(){
	freopen("1.out","w",stdout);
	cout.tie(0);
	int x=1,y=1,z=2,sum=23;
	cout<<1<<endl<<5<<endl<<23<<endl;
	for(int i=4;i<=10000000;i++){
		x=y;
		y=z;
		z=(x+y)%m;
		sum+=i*i%m*z%m;
		sum%=m;
		cout<<sum<<endl;
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
int m=1000000007;
vector<vector<int> > mul(vector<vector<int> > a,vector<vector<int> > b){
	vector<vector<int> > c(a.size(),vector<int>(b[0].size()));
	for(int i=0;i<a.size();i++){
		for(int j=0;j<b[0].size();j++){
			for(int k=0;k<a[0].size();k++){
				c[i][j]+=a[i][k]*b[k][j];
				c[i][j]%=m;
			}
		}
	}
	return c;
}
vector<vector<int> > qp(vector<vector<int> > a,int n){
	vector<vector<int> > b(a[0].size(),vector<int>(a.size()));
	for(int i=0;i<b.size();i++){
		b[i][i]=1;
	}
	while(n){
		if(n%2)b=mul(a,b);
		a=mul(a,a);
		n/=2;
	}
	return b;
}
signed main(){
	freopen(".in","r",stdin);
	freopen(".ans","w",stdout);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vector<vector<int> > a(2,vector<int>(2));
	a[0][0]=1;
	a[0][1]=1;
	a[1][0]=1;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		vector<vector<int> > b=qp(a,x+2),c=qp(a,x+3),d=qp(a,x+4);
		cout<<((x%m*x%m*b[1][0]%m-(2*x-1)%m*c[1][0]%m+2*d[1][0]-8)%m+m)%m<<endl;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen(".in","w",stdout);
	srand(time(0));
	cout<<1000000<<endl;
	for(int i=1;i<=1000000;i++){
		cout<<1ll*rand()*rand()*rand()*rand()%900000000000000000+100000000000000000<<endl;
	}
}

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen(".in","w",stdout);
	cout<<10000000<<endl;
	for(int i=1;i<=100000000;i++){
		cout<<i<<endl;
	}
}