#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]);
D[1][0]=(A[1][0]*aux[0][0] + A[1][1]*aux[1][0]);
D[0][1]=(A[0][0]*aux[0][1] + A[0][1]*aux[1][1]);
D[1][1]=(A[1][0]*aux[0][1] + A[1][1]*aux[1][1]);
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]);
C[1][0]=(A[1][0]*A[0][0] + A[1][1]*A[1][0]);
C[0][1]=(A[0][0]*A[0][1] + A[0][1]*A[1][1]);
C[1][1]=(A[1][0]*A[0][1] + A[1][1]*A[1][1]);
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]);
D[1][0]=(A[1][0]*aux[0][0] + A[1][1]*aux[1][0]);
D[0][1]=(A[0][0]*aux[0][1] + A[0][1]*aux[1][1]);
D[1][1]=(A[1][0]*aux[0][1] + A[1][1]*aux[1][1]);
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+CiNpbmNsdWRlPGlvc3RyZWFtPgojZGVmaW5lIE1PRCAxMDAwMDAwMDA3CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVuc2lnbmVkIGxvbmcgbG9uZyBBWzJdWzJdPXsxLDEsMSwwfTsKdW5zaWduZWQgbG9uZyBsb25nIEJbMl1bMl09ezEsMSwxLDB9Owp1bnNpZ25lZCBsb25nIGxvbmcgQ1syXVsyXTsKaW50IG1vZF9wb3cxKHVuc2lnbmVkIGxvbmcgbG9uZyBleHBvbmVudCkKewppZiAoZXhwb25lbnQgPT0gMCkgcmV0dXJuIDE7CnVuc2lnbmVkIGxvbmcgbG9uZyBhdXhbMl1bMl09ezEsMCwwLDF9Owp1bnNpZ25lZCBsb25nIGxvbmcgRFsyXVsyXTsKd2hpbGUoZXhwb25lbnQgPiAxKQp7CiAgICBpZiAoZXhwb25lbnQgJSAyICE9IDApCiAgICAgewogIERbMF1bMF09KEFbMF1bMF0qYXV4WzBdWzBdICsgQVswXVsxXSphdXhbMV1bMF0pOwogIERbMV1bMF09KEFbMV1bMF0qYXV4WzBdWzBdICsgQVsxXVsxXSphdXhbMV1bMF0pOwoKICBEWzBdWzFdPShBWzBdWzBdKmF1eFswXVsxXSArIEFbMF1bMV0qYXV4WzFdWzFdKTsKICBEWzFdWzFdPShBWzFdWzBdKmF1eFswXVsxXSArIEFbMV1bMV0qYXV4WzFdWzFdKTsKCgogICAgZm9yKGludCBpPTA7aTwyOysraSkKICAgIGZvcihpbnQgaj0wO2o8MjsrK2opCiAgICBhdXhbaV1bal09RFtpXVtqXTsKCiAgICAgfQoKCiAgICBDWzBdWzBdPShBWzBdWzBdKkFbMF1bMF0gKyBBWzBdWzFdKkFbMV1bMF0pOwogICAgQ1sxXVswXT0oQVsxXVswXSpBWzBdWzBdICsgQVsxXVsxXSpBWzFdWzBdKTsKCiAgICBDWzBdWzFdPShBWzBdWzBdKkFbMF1bMV0gKyBBWzBdWzFdKkFbMV1bMV0pOwogICAgQ1sxXVsxXT0oQVsxXVswXSpBWzBdWzFdICsgQVsxXVsxXSpBWzFdWzFdKTsKCgogICAgZm9yKGludCBpPTA7aTwyOysraSkKICAgIGZvcihpbnQgaj0wO2o8MjsrK2opCiAgICBBW2ldW2pdPUNbaV1bal07CgogICAgICAgIGV4cG9uZW50IC89IDI7Cn0KCiAgRFswXVswXT0oQVswXVswXSphdXhbMF1bMF0gKyBBWzBdWzFdKmF1eFsxXVswXSk7CiAgRFsxXVswXT0oQVsxXVswXSphdXhbMF1bMF0gKyBBWzFdWzFdKmF1eFsxXVswXSk7CgogIERbMF1bMV09KEFbMF1bMF0qYXV4WzBdWzFdICsgQVswXVsxXSphdXhbMV1bMV0pOwogIERbMV1bMV09KEFbMV1bMF0qYXV4WzBdWzFdICsgQVsxXVsxXSphdXhbMV1bMV0pOwoKCgogICAgZm9yKGludCBpPTA7aTwyOysraSkKICAgIGZvcihpbnQgaj0wO2o8MjsrK2opCiAgICBBW2ldW2pdPURbaV1bal07CgoKfQppbnQgbWFpbigpCnsKCgogICAgaW50IHQsZyxHOy8vLHIsRzsKICAgIHVuc2lnbmVkIGxvbmcgbG9uZyByLG47CiAgICBzY2FuZigiJWQiLCZ0KTsKICAgIC8vZnVuKCk7CiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAgICAgLy9zY2FuZigiJWQlZCIsJm4sJmcpOwogICAgICAgIGNpbj4+bjsKICAgICAgICBpZihuPT0xKQogICAgICAgIHI9MTsKICAgICAgICBlbHNlIGlmKG49PTIpCiAgICAgICAgcj0yOwogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgbW9kX3BvdzEobi0yKTsKICAgICAgICByPSgyKkFbMF1bMF0gKyBBWzBdWzFdKSVNT0Q7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIGNvdXQ8PHI7CiAgICAgICAKICAgIH0KfQo=