#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define matrix vector<vector >
ll n;
vectorb;
matrix multiply(matrix A,matrix B)
{
matrix c;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
{
c[i][j]= (c[i][j]+A[i][k]*B[k][j])%mod;
}
}
}
return c;
}
matrix power(matrix m,ll p)
{
if(p==0)
{
return m;
}
if(p&1)
{
return multiply(m,power(m,p-1));
}
matrix x=power(m,p/2);
return multiply(x,x);
}
ll fib(ll n)
{
ll finalans=0;
if(n==0||n==1)
{
return 1;
}
matrix m;
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
if(i+j==0)
{
m[i][j]=0;
}
else{
m[i][j]=1;
}
}
}
m=power(m,n-1);
finalans +=((m[0][0]*1ll)+(m[0][1]*1ll))%mod;
return finalans%mod;
}
int main()
{
int t;
cin>>t;
while(t–)
{
cin>>n;
ll ans=fib(n);
if(ans<0)
{
ans +=mod;
}
cout<<ans<<endl;
}
}