This is how I implement matrix exponentiation 190118918 (in this example, for the problem Fibonacci)

But I encountered this problem before and got TLE after implementing matrix exponentiation.

My solution code was:

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

#define nl "\n"
#define ll long long
#define fo(i,n) for(i=0;i<n;i++)
#define fop(i,x,n) for(i=x;i<=n;i++)
typedef vector<int> vi;
typedef vector<ll> vl;

const int mod = 1e9+7;
const int N = 2e5+5;

vector<vl> mul(vector<vl> a,vector<vl> b){
    ll n=a.size(),i,j,k;
    vector<vl> ans(n,vl(n,0));
    fo(i,n) fo(j,n) fo(k,n) ans[i][j]=(ans[i][j]+a[i][k]*b[k][j]%mod)%mod;
    return ans;
}

vector<vl> mpow(vector<vl> a,ll b){
    ll i,n=a.size();
    vector<vl> res(n,vl(n,0));
    fo(i,n) res[i][i]=1;
    while(b){
        if(b&1) res=mul(res,a);
        a=mul(a,a);
        b>>=1;
    }
    return res;
}

void solve(int test){
    ll n;
    char c;
    cin>>n>>c;
    if(n==3&&c=='g'){
        cout<<4<<nl;
        return;
    }
    if(n==3&&c=='f'){
        cout<<5<<nl;
        return;
    }
    if(n==4&&c=='f'){
        cout<<11<<nl;
        return;
    }
    if(n==1){
        cout<<1<<nl;
        return;
    }
    if(n==2){
        cout<<2<<nl;
        return;
    }
    vector<vl> v={{1,2,1,1,0},{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0}};
    v=mpow(v,n-4);
    vector<vl> v1={{2,0,1},{1,0,0},{0,1,0}};
    v1=mpow(v1,n-3);
    if(c=='f'){
        cout<<(11*v[0][0]+5*v[0][1]+2*v[0][2]+v[0][3]+v[0][4])%mod<<nl;
    }else{
        cout<<(4*v1[0][0]+2*v1[0][1]+v1[0][2])%mod<<nl;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int i,t=1;
    cin>>t;
    fo(i,t){
        solve(i+1);
    }
    return 0;
}

According to me, it should run in O(QlogN), which should pass, but it gave TLE in almost all testcases. Please let me know why it failed

P.S:- The recurrences after solving came out to be: f(n)=f(n-1)+2*f(n-2)+f(n-3)+f(n-4) g(n)=2*g(n-1)+g(n-3)