矩阵快速幂

//https://nanti.jisuanke.com/t/A2022
#include 
//#define endl '\n'
#define lose {printf("NO\n");return;}
#define win {printf("YES\n");return;}
#define all(A) (A).begin(),(A).end()
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define PER(I, A, B) for (int I = (A); I >= (B); --I)
#define DB(A) cout<<(A)<
#define MP make_pair
#define LL long long
#define ull unsigned long long
#define int LL
using namespace std;
#define DB1(args...) do { cout << #args << " : "; dbg(args); } while (0)
void dbg() { std::cout << "  #\n"; }
template
void dbg(T a, Args...args) { std::cout << a << ' '; dbg(args...); }
//var
const int maxn=2e5+10;
const int MAX=1000;
const int inf=0x3f3f3f3f;   
const int mod=1e9+7;
//head


#define NUM 9  
int MAXN=NUM;  
struct Matrix 
{  
    int a[NUM][NUM];  
    void init()           
    {  
        memset(a,0,sizeof(a));  
        for(int i=0;i>n;
	if(n == 1)  printf("3\n");
        else if(n == 2) printf("9\n");
        
        
    else
    {
    	Matrix res,ans = {
            0,0,0, 1,0,0, 1,0,0,
            1,0,0, 0,0,0, 1,0,0,
            1,0,0, 1,0,0, 1,0,0,

            0,1,0, 0,1,0, 0,0,0,
            0,1,0, 0,0,0, 0,1,0,
            0,0,0, 0,1,0, 0,1,0,

            0,0,1, 0,0,1, 0,0,1,
            0,0,1, 0,0,0, 0,0,1,
            0,0,1, 0,0,1, 0,0,0
        }; 
        //DB1(ans.a[3][2]);
        //output(ans);
        //return;
	    int ant=0;
	    res=pow(ans,n-2);
	    //output(res);
	    for(int i = 0;i < MAXN;i++)
	                for(int j = 0;j < MAXN;j++)
	                    ant = (ant + res.a[i][j]) % mod;
	   printf("%lld\n",ant);
    }
	

} 
signed main()
{
    // freopen("read.txt", "r", stdin);
    // freopen("ans.txt", "w", stdout);
    int TestCase = 1;
    cin>>TestCase;
    while (TestCase--)
    {
        solve();
    }
    char EndFile = getchar();
    EndFile = getchar();
    return 0;
}