#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;
       
    }
}