Matrix Expo

/*
    Author : M. A. Rafsan Mazumder
    *** Matrix Exponentiation ***
    Complexity : O(n^3 * log(n))
    Code : LightOJ 1096 - Finding nth term for -
           f(n) = a*f(n-1) + b*f(n-3) + c , if(n>2)
           f(n) = 0 , if(n<=2)
*/

#include <bits/stdc++.h>

using namespace std;

#define dim 4 // dimension of the matrix
#define MOD 10007
#define ll long long
ll n, a, b, c;

struct matrix{
    ll M[dim][dim];

    // constructor. Make an empty array.
    matrix(){
        memset(M, 0, sizeof M);
    }

    // constant matrix (M)
    void unit_matrix(){
        M[0][0] = a, M[0][1] = 0, M[0][2] = b, M[0][3] = 1;
        M[1][0] = 1, M[1][1] = 0, M[1][2] = 0, M[1][3] = 0;
        M[2][0] = 0, M[2][1] = 1, M[2][2] = 0, M[2][3] = 0;
        M[3][0] = 0, M[3][1] = 0, M[3][2] = 0, M[3][3] = 1;
    }

    matrix operator* (matrix N){
        matrix mul;
        for(ll i=0; i<dim; i++){
            for(ll j=0; j<dim; j++){
                for(ll k=0; k<dim; k++){
                    mul.M[i][j] = (mul.M[i][j]%MOD + ((M[i][k]%MOD)*(N.M[k][j]%MOD))%MOD)%MOD;
                }
            }
        }
        return mul;
    }
};

matrix pow_matrix(matrix A, ll p)
{
    if(p == 1) return A;

    matrix ret = pow_matrix(A, p/2);
    ret = ret * ret;
    if(1&p) ret = ret * A;

    return ret;
}

int main()
{
    ll cases;
    scanf("%lld", &cases);
    ll caseno = 0;
    while(cases--){
        scanf("%lld %lld %lld %lld", &n, &a, &b, &c);
        if(n <= 2){
            printf("Case %lld: %lld\n", ++caseno, 0);
            continue;
        }
        matrix t;
        t.unit_matrix();
        t = pow_matrix(t, n-2);
        ll ans = (t.M[0][3]%MOD) * (c%MOD);
        printf("Case %lld: %lld\n", ++caseno, ans%MOD);
    }
}