Optimisasi kode agar tidak Time Limit

Halo, disini saya mempunyai soal yang memiliki sebuah fungsi f(n)= 1, n=0 f(n)= 2, n=1 f(n)= a+b, n=2 f(n)= 5, n=3 f(n)= [a f(n-2)+b] mod 10^9 + 7, n= genap, n>3 f(n)= [4 f(n-2)-4f(n-4)+((n-1)^2)/4] mod 10^9+7, n=ganjil, n >3 dengan t adalah sebuah berapa testcase

Disini saya sudah melakukan beberapa optimisasi yaitu menggunakan define mod agar tidak perlu menghitung lagi dengan pow dan mengubah pembagian yang melibatkan (n-1)^2 /4 dalam rumus untuk nilai ganjil menjadi operasi modulo yang lebih efisien menggunakan sifat dari Galois Field. Tetapi tetap saja, tidak berhasil. Time Limit disini adalah 1s

#include <stdio.h>

#define ll long long
#define mod 1000000007 

ll invrs_mod(ll x){
    ll res = 1;
    ll pow = mod - 2; 
    while (pow){
        if (pow%2)
        res = (res * x) % mod;
        x = (x*x) % mod;
        pow = pow / 2;
    }
    return res;
}

ll f_FUNC(int a, int b, int n) {
    if (n == 0) return 1;
    if (n == 1) return 2;
    if (n == 2) return (a + b) % mod;
    if (n == 3) return 5;

    ll f_prev4 = 1; 
    ll f_prev3 = 2; 
    ll f_prev2 = (a + b) % mod; 
    ll f_prev1 = 5; 
    ll f_cur = 0;
    ll invrs_4 = invrs_mod(4);

/*
    for (int i = 4; i <= n; i++) {
        if (i % 2 == 0) {
            f_cur = (a * f_prev2 + b) % mod;
        } else {
            f_cur = (4 * f_prev2 - 4 * f_prev4 + ((ll)(i - 1) * (i - 1)) / 4) % mod;
            if (f_cur < 0) f_cur += mod; 
        }
        f_prev4 = f_prev3;
        f_prev3 = f_prev2;
        f_prev2 = f_prev1;
        f_prev1 = f_cur;
    }

    return f_cur;
}
*/
/*
for (int i = 4; i <= n; i++) {
        if (i % 2 == 0) {
            f_cur = (a * f_prev2 + b) % mod;
        } else {
            ll temp = (4 * f_prev2 - 4 * f_prev4 + ((ll)(i - 1) * (i - 1)) / 4) % mod;
            f_cur = (4 * f_prev2 - 4 * f_prev4 + ((ll)(i - 1) * (i - 1) % mod) * invrs_4 % mod) % mod;
            if (f_cur < 0) f_cur += mod;  
        }
*/
for (int i = 4; i <= n; i++) {
        ll square = (ll)(i - 1) * (i - 1) % mod;  
        if (i % 2 == 0) {
            f_cur = (a * f_prev2 + b) % mod;
        } else {
            f_cur = (4 * f_prev2 - 4 * f_prev4 + (square * invrs_4) % mod) % mod;
            if (f_cur < 0) f_cur += mod;  
        }
        f_prev4 = f_prev3;
        f_prev3 = f_prev2;
        f_prev2 = f_prev1;
        f_prev1 = f_cur;
    }

    return f_cur;
}

int main() {
    int a, b, n, t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++){
    scanf("%d %d %d", &a, &b, &n);
    printf("%lld\n", f_FUNC(a, b, n));
    }
    return 0;
}


/*
#include <stdio.h>

#define ll long long
#define mod 1000000007 //10^9+7

ll f(int n, ll a, ll b) {
    if (n == 0) return 1;             
    if (n == 1) return 2;             
    if (n == 2) return (a + b) % mod;     
    if (n == 3) return 5;             

    ll fn_minus_4 = 1; 
    ll fn_minus_2 = 2; 
    ll fn = 0;

    for (int i = 4; i <= n; i++) {
        if (i % 2 == 0) {
            fn = (a * fn_minus_2 + b) % mod;
        } else {
            fn = (4 * fn_minus_2 - 4 * fn_minus_4 + ((i-1) * (i-1) / 4)) % mod; 
            if (fn < 0) fn += mod; 
        }
        fn_minus_4 = fn_minus_2;
        fn_minus_2 = fn;
    }

    return fn;
}

int main() {
    ll a, b;
    int n;

    printf("Masukkan nilai a, b, dan n: ");
    scanf("%lld %lld %d", &a, &b, &n);

    printf("f(%d) = %lld\n", n, f(n, a, b));
    return 0;
}

*/