Matrix Exponential (Powers of a Matrix)

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

#define siz 1000005

typedef long long ll;

struct Matrix{

    ll t[3][3];

}init,in;



void buildMat(){

    for(int i=0;i<3;i++)

        for(int j=0;j<3;j++)

            init.t[i][j]=1;

    init.t[1][1]=init.t[1][2]=init.t[2][0]=init.t[2][2]=0;

    in=init;

}

Matrix mul(Matrix x, Matrix y, ll m){

    Matrix temp={};

    for(int i=0;i<3;i++)

        for(int j=0;j<3;j++)

            for(int k=0;k<3;k++)

                temp.t[i][j]+=(x.t[i][k]*y.t[k][j])%m;

    return temp;

}

ll res(ll n, ll m){

    Matrix x=init, y=in;

    while(n>0){

        if(n&1) x=mul(x,y,m);

        y=mul(y,y,m);

        n >>= 1;

    }

    return ((x.t[0][0]*3)+(x.t[0][1]*2)+(x.t[0][2]*1))%m;

}

int main()

{

    ll n,m;

    buildMat();

    while(scanf("%lld",&n)==1){

        if(n==0) break;

        ll mod=1000000009;

        if(n==1) puts("0");

        else if(n==2) puts("1");

        else if(n==3) puts("2");

        else if(n==4) puts("3");

        else cout<<res(n-5,mod)<<endl;

    }

    return 0;

}