#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#define MOD 1000000007
using namespace std;
unsigned long long A[2][2]={1,1,1,0};
unsigned long long B[2][2]={1,1,1,0};
unsigned long long C[2][2];
int mod_pow1(unsigned long long exponent)
{
if (exponent == 0) return 1;
unsigned long long aux[2][2]={1,0,0,1};
unsigned long long D[2][2];
while(exponent > 1)
{
if (exponent % 2 != 0)
{
D[0][0]=(A[0][0]*aux[0][0] + A[0][1]*aux[1][0])%MOD;
D[1][0]=(A[1][0]*aux[0][0] + A[1][1]*aux[1][0])%MOD;
D[0][1]=(A[0][0]*aux[0][1] + A[0][1]*aux[1][1])%MOD;
D[1][1]=(A[1][0]*aux[0][1] + A[1][1]*aux[1][1])%MOD;
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
aux[i][j]=D[i][j];
}
C[0][0]=(A[0][0]*A[0][0] + A[0][1]*A[1][0])%MOD;
C[1][0]=(A[1][0]*A[0][0] + A[1][1]*A[1][0])%MOD;
C[0][1]=(A[0][0]*A[0][1] + A[0][1]*A[1][1])%MOD;
C[1][1]=(A[1][0]*A[0][1] + A[1][1]*A[1][1])%MOD;
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
A[i][j]=C[i][j];
exponent /= 2;
}
D[0][0]=(A[0][0]*aux[0][0] + A[0][1]*aux[1][0])%MOD;
D[1][0]=(A[1][0]*aux[0][0] + A[1][1]*aux[1][0])%MOD;
D[0][1]=(A[0][0]*aux[0][1] + A[0][1]*aux[1][1])%MOD;
D[1][1]=(A[1][0]*aux[0][1] + A[1][1]*aux[1][1])%MOD;
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
A[i][j]=D[i][j];
}
int main()
{
int t,g,G;//,r,G;
unsigned long long r,n;
scanf("%d",&t);
//fun();
while(t--)
{
//scanf("%d%d",&n,&g);
cin>>n;
if(n==1)
r=1;
else if(n==2)
r=2;
else
{
mod_pow1(n-2);
r=(2*A[0][0] + A[0][1])%MOD;
}
cout<<r;
}
}
I2luY2x1ZGU8bWF0aC5oPgojaW5jbHVkZTxzdGRpby5oPgojaW5jbHVkZTxzdGRsaWIuaD4KI2luY2x1ZGU8c3RyaW5nLmg+CiNpbmNsdWRlPGlvc3RyZWFtPgojZGVmaW5lIE1PRCAxMDAwMDAwMDA3CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVuc2lnbmVkIGxvbmcgbG9uZyBBWzJdWzJdPXsxLDEsMSwwfTsKdW5zaWduZWQgbG9uZyBsb25nIEJbMl1bMl09ezEsMSwxLDB9Owp1bnNpZ25lZCBsb25nIGxvbmcgQ1syXVsyXTsKaW50IG1vZF9wb3cxKHVuc2lnbmVkIGxvbmcgbG9uZyBleHBvbmVudCkKewppZiAoZXhwb25lbnQgPT0gMCkgcmV0dXJuIDE7CnVuc2lnbmVkIGxvbmcgbG9uZyBhdXhbMl1bMl09ezEsMCwwLDF9Owp1bnNpZ25lZCBsb25nIGxvbmcgRFsyXVsyXTsKd2hpbGUoZXhwb25lbnQgPiAxKQp7CiAgICBpZiAoZXhwb25lbnQgJSAyICE9IDApCiAgICAgewogIERbMF1bMF09KEFbMF1bMF0qYXV4WzBdWzBdICsgQVswXVsxXSphdXhbMV1bMF0pJU1PRDsKICBEWzFdWzBdPShBWzFdWzBdKmF1eFswXVswXSArIEFbMV1bMV0qYXV4WzFdWzBdKSVNT0Q7CgogIERbMF1bMV09KEFbMF1bMF0qYXV4WzBdWzFdICsgQVswXVsxXSphdXhbMV1bMV0pJU1PRDsKICBEWzFdWzFdPShBWzFdWzBdKmF1eFswXVsxXSArIEFbMV1bMV0qYXV4WzFdWzFdKSVNT0Q7CgoKICAgIGZvcihpbnQgaT0wO2k8MjsrK2kpCiAgICBmb3IoaW50IGo9MDtqPDI7KytqKQogICAgYXV4W2ldW2pdPURbaV1bal07CgogICAgIH0KCgogICAgQ1swXVswXT0oQVswXVswXSpBWzBdWzBdICsgQVswXVsxXSpBWzFdWzBdKSVNT0Q7CiAgICBDWzFdWzBdPShBWzFdWzBdKkFbMF1bMF0gKyBBWzFdWzFdKkFbMV1bMF0pJU1PRDsKCiAgICBDWzBdWzFdPShBWzBdWzBdKkFbMF1bMV0gKyBBWzBdWzFdKkFbMV1bMV0pJU1PRDsKICAgIENbMV1bMV09KEFbMV1bMF0qQVswXVsxXSArIEFbMV1bMV0qQVsxXVsxXSklTU9EOwoKCiAgICBmb3IoaW50IGk9MDtpPDI7KytpKQogICAgZm9yKGludCBqPTA7ajwyOysraikKICAgIEFbaV1bal09Q1tpXVtqXTsKCiAgICAgICAgZXhwb25lbnQgLz0gMjsKfQoKICBEWzBdWzBdPShBWzBdWzBdKmF1eFswXVswXSArIEFbMF1bMV0qYXV4WzFdWzBdKSVNT0Q7CiAgRFsxXVswXT0oQVsxXVswXSphdXhbMF1bMF0gKyBBWzFdWzFdKmF1eFsxXVswXSklTU9EOwoKICBEWzBdWzFdPShBWzBdWzBdKmF1eFswXVsxXSArIEFbMF1bMV0qYXV4WzFdWzFdKSVNT0Q7CiAgRFsxXVsxXT0oQVsxXVswXSphdXhbMF1bMV0gKyBBWzFdWzFdKmF1eFsxXVsxXSklTU9EOwoKCgogICAgZm9yKGludCBpPTA7aTwyOysraSkKICAgIGZvcihpbnQgaj0wO2o8MjsrK2opCiAgICBBW2ldW2pdPURbaV1bal07CgoKfQppbnQgbWFpbigpCnsKCgogICAgaW50IHQsZyxHOy8vLHIsRzsKICAgIHVuc2lnbmVkIGxvbmcgbG9uZyByLG47CiAgICBzY2FuZigiJWQiLCZ0KTsKICAgIC8vZnVuKCk7CiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAgICAgLy9zY2FuZigiJWQlZCIsJm4sJmcpOwogICAgICAgIGNpbj4+bjsKICAgICAgICBpZihuPT0xKQogICAgICAgIHI9MTsKICAgICAgICBlbHNlIGlmKG49PTIpCiAgICAgICAgcj0yOwogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgbW9kX3BvdzEobi0yKTsKICAgICAgICByPSgyKkFbMF1bMF0gKyBBWzBdWzFdKSVNT0Q7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIGNvdXQ8PHI7CiAgICAgICAKICAgIH0KfQo=