LOCKER - Magic of the locker

#include <bits/stdc++.h>

#define int long long

#define pb push_back

#define fi first

#define se second

#define pii pair<int,int>

#define vi vector<int>

using namespace std;

int m=1e9+7;

int modexp(int x,int n){

    if(n==0) return 1;

    if(n%2==0) return (modexp(((x%m)*(x%m))%m,n/2))%m;

    return ((x%m)*(modexp(((x%m)*(x%m))%m,(n-1)/2))%m)%m;

}

int32_t main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    int t;

    cin>>t;

    while(t--){

        int x;

        cin>>x;

        if(x==1){

            cout<<1<<endl;

            continue;

        }

        if(x==2){

            cout<<2<<endl;

            continue;

        }

        if(x%3==0) cout<<modexp(3,x/3)<<'\n';

        else if(x%3==2) cout<<(((modexp(3,x/3))%m)*(2))%m<<'\n';

        else{

            cout<<((modexp(3,((x/3)-1))%m)*4)%m<<'\n';

        }

    }

    return 0;

}