Foj 1683 纪念SlingShot

//Author: xiaowuga
//矩阵：3 2 7 0  5
//     1,0,0,0  3
//     0,1,0,0  1
//     3,2,7,1  9
//
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
#define size 4
#define MOD 2009
using namespace std;
typedef long long ll;
struct Matrix{
    ll mat[10][10];
    void clear(){
        memset(mat,0,sizeof(mat));
    }
    Matrix operator * (const Matrix & m) const{
        Matrix tmp;
        for(int i=0;i<size;i++)
            for(int j=0;j<size;j++){
                tmp.mat[i][j]=0;
                for(int k=0;k<size;k++){
                    tmp.mat[i][j]+=mat[i][k]*m.mat[k][j]%MOD;
                    tmp.mat[i][j]%=MOD;
                }
            }
        return tmp;
    }
};
Matrix POW(Matrix m,ll k){
    Matrix ans;
    ans.clear();
    for(int i=0;i<size;i++) ans.mat[i][i]=1;
    while(k){
        if(k&1) ans=ans*m;
        k/=2;
        m=m*m;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    int nCase;
    cin>>nCase; 
    for(int i=1;i<=nCase;i++){
        ll n,f[4]={5,3,1,9};
        cin>>n;
        ll ans=0;
        if(n<=2){
            for(int j=2;j>=2-n;j--)
                ans+=f[j];
            cout<<"Case "<<i<<": "<<ans<<endl;
        }
        else{
            Matrix m;
            m.clear();
            m.mat[0][0]=m.mat[3][0]=3;
            m.mat[0][1]= m.mat[3][1]=2;
            m.mat[0][2]=m.mat[3][2]=7;
            m.mat[1][0]=m.mat[2][1]= m.mat[3][3]=1;
            //for(int a=0;a<4;a++){
                //for(int b=0;b<4;b++) cout<<m.mat[a][b]<<" ";
                //cout<<endl;
            Matrix a=POW(m,n-2);
            for(int k=0;k<4;k++){
                ans+=a.mat[3][k]*f[k]%MOD;
                ans%=MOD;
            }
            cout<<"Case "<<i<<": "<<ans<<endl;
        } 
            
    }
    return 0;
}