Fast Matrix Multiplication

#include<bits/stdc++.h>
#define ll long long
#define Matrix vector< vector < long long > >
using namespace std;
Matrix D;
long long MOD=1000000007;
void Resize_Matrix(long long n , long long m , Matrix &M){
    M.clear();
    for(int j=0;j<n;j++) {
        M.push_back( vector< long long >() );
        M[j].clear();
        M[j].resize(m);
        for(int i=0;i<m;i++) M[j][i]=0;
    }
}
Matrix Matrix_Multiplication(Matrix A , Matrix B){
    Matrix Ans; long long n , m;
    Resize_Matrix(n=A.size() , m=A[0].size() , Ans);
    for(long long j=0;j<n;j++){
        for(long long i=0;i<n;i++){
            Ans[j][i]=0;

            for(long long k=0;k<n;k++){
                Ans[j][i]+=A[j][k]*B[k][i];
                Ans[j][i]%=MOD;
            }
        }
    }
    return Ans;
}
Matrix Matrix_Exponentiation(Matrix M , long long power){
    if(power==0)return D;
    if(power==1) return M;
    Matrix ret;
    ret=Matrix_Exponentiation(M , power/2);
    ret=Matrix_Multiplication(ret , ret);
    if(power%2==1) ret=Matrix_Multiplication(ret,M);
    return ret;
}

int main()
{
int t;cin>>t;
while(t--)
    {ll k;cin>>k;
    if(k==1){cout<<3<<endl;continue;}
    Matrix F;
    Resize_Matrix(3,3,F);
    Resize_Matrix(3,3,D);
    int q=1;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++){
        D[i][j]=1;
        F[j][i]=q;
        q++;
    }
    //for(int i=0;i<3;i++)F[i][i]=1;
ll sum=0;
    Matrix R;
    Resize_Matrix(3,3,R);
    R=Matrix_Exponentiation(F,k-1);
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)sum=(sum%MOD+R[i][j]%MOD)%MOD;
    cout<<sum<<endl;
    }
    return 0;
}