#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
const int mod=1e9+7;
const int N=10;
int n,t;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
struct mat{
    int a[N][N],h,l;
}a,res,ans;
mat operator *(mat a,mat b){
    mat t;
    for(int i=1;i<=a.h;i++)
	for(int j=1;j<=b.l;j++)
	    t.a[i][j]=0;//清零
    for(int i=1;i<=a.h;i++)
	for(int j=1;j<=b.l;j++)
	    for(int k=1;k<=a.l;k++)
		t.a[i][j]=(t.a[i][j]+(a.a[i][k]*b.a[k][j])%mod)%mod;
    t.h=a.h,t.l=b.l;
    return t;
}
void qpow(int b){
    for(;b;b>>=1){
	if(b&1) res=res*a;
	a=a*a;
    }
}
signed main(){
    t=read();
    while(t--){
	for(int i=1;i<=2;i++)
	    for(int j=1;j<=2;j++) res.a[i][j]=0,a.a[i][j]=0,ans.a[i][j]=0;
	for(int i=1;i<=2;i++) res.a[i][i]=1;//单位矩阵
	res.h=2,res.l=2;
	a.h=2,a.l=2;
	ans.h=1,ans.l=2;
	a.a[1][1]=a.a[1][2]=a.a[2][1]=1;
	ans.a[1][2]=1;
	n=read();
	qpow(n-1);
	ans=ans*res;
	int real=0;
	real=((real+ans.a[1][1])%mod+ans.a[1][2])%mod;
	real=(real+ans.a[1][1])%mod;
	cout<<real<<endl;
    }
}