CSUMD-CC.cpp

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define inf 2e18
int MOD=1000000007;//998244353;
const int nn=1000050;
bool prime[nn]; //array to store precalculated primes till 10^6
void cal_primes(){memset(prime,true,sizeof(prime)); for(int i=2;i<=sqrt(nn);++i){ if(prime[i]==true){ for(int j=i*i;j<=nn;j+=i){prime[j]=false;}}}}

int m[2][2]={{2,2},{1,0}};
int f[2][2]={{2,2},{1,0}};

void multiply(int A[2][2],int B[2][2])
{
    int x=((A[0][0]*B[0][0])+(A[0][1]*B[1][0]));
    int y=((A[0][0]*B[0][1])+(A[0][1]*B[1][1]));
    int z=((A[1][0]*B[0][0])+(A[1][1]*B[1][0]));
    int w=((A[1][0]*B[0][1])+(A[1][1]*B[1][1]));

    A[0][0]=x%MOD;
    A[0][1]=y%MOD;
    A[1][0]=z%MOD;
    A[1][1]=w%MOD;
}

void power(int f[2][2],int n)
{
    if(n==0)
    return;

    while(n>0)
    {
        if(n&1)
            multiply(f,m);
        multiply(m,m);
        n=(n>>1);
    }
}
void val(int n)
{
    if(n==1)
        return;
    power(f,n-1);
}
void solve(int t)
{
    int testcases=t;
    while(t--)
    {
        //cerr<<"Case #"<<(testcases-t)<<": "<<endl;
        int n;cin>>n;
        f[0][0]=2;f[0][1]=2;f[1][0]=1;f[1][1]=0;
        m[0][0]=2;m[0][1]=2;m[1][0]=1;m[1][1]=0;

        if(n<2)
            cout<<1<<endl;
        else if(n==2)
            cout<<3<<endl;
        else
        {
            val(n-2);
            int val=(((3*f[0][0])+(f[0][1]))%MOD);
            cout<<val<<endl;
        }
    }
}

main()
{
    auto start=chrono::system_clock::now();
    {
        #ifndef ONLINE_JUDGE
            freopen("input.txt","r",stdin);
            freopen("output.txt","w",stdout);
            freopen("error.txt","w",stderr);
        #endif
        ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        int t=1;
        cin>>t;
        solve(t);
    }
    auto end=chrono::system_clock::now();
    chrono::duration<double> elapsed=end-start;
//  cout<<endl<<"Time taken: "<<elapsed.count()<<" sec";
    return 0;
}