이전에 글썼던 뉴비입니다. ㅜㅜ

[[problem:TILING]]
도움을 받아 코드를 완성했으나, 오답이 뜨고 있네요.
점화식은 아래와 같이 계산했고,

T[N]= T[N-1]+2T[N-2]+5T[N-3]

선형 점화식에 대해서 한정적으로 사용할 수있는
Matrix 기법을 사용했습니다.
위 점화식을 바탕으로 3*3 Matrix 를 아래와 같이 정의하였고,

1 2 5
1 0 0
0 1 0

N이 1일 경우엔 1
2일 경우엔 3
3일 경우엔 10을 리턴하도록 하고,

N이 4이상일경우

위 행렬에 에대해 (N-3) POW연산 후 아래 행렬의 값을 곱하여
리턴해주도록 하였습니다.

10
3
1

아래코드에서 잘못된 것으로 예상되는것이
1. modulo연산...
2. 행렬 연산
3. 점화식 자체가 틀림...
무엇이잘못되었을까요.. 조언 부탁드립니다.ㅠㅠ
~~~ c++
#include
using namespace std;

int N;
struct matrix {
int r, c;
int** mat;

matrix(int r, int c, int v[]) : r(r), c(c) {
    mat = new int*[r];
    for (int i=0; i < r; ++i) {
        mat[i] = new int[c];
    }
    for (int i=0; i < r; ++i) {
        for (int j=0; j < c; ++j) {
            mat[i][j] = v[i*c+j];
        }
    }
}
matrix(matrix& other){
    r=other.c; c = other.c;
    mat = new int*[r];
    for (int i=0; i < r; ++i) {
        mat[i] = new int[c];
    }
    copy(other);
}
~matrix() {
    for (int i=0; i < r; ++i) {
        if (c > 1) {
            delete[] mat[i];
        } else {
            delete mat[i];
        }
    }
    if (r > 1) {
        delete[] mat;
    } else {
        delete mat;
    }
}
void identify() {
    for (int i=0; i < r; ++i) {
        for(int j=0; j < c; ++j) {
            mat[i][j] = (i==j);
        }
    }
}
void copy(matrix& other) {
    this->r = other.r;
    this->c = other.c;
    for (int i=0; i < r; ++i) {
        for (int j=0; j < c; ++j) {
            mat[i][j] = other.mat[i][j];
        }
    }
}
void multiply(matrix& out, matrix& other) {
    for (int i=0; i < this->r; ++i) {
        for (int j=0; j < other.c; ++j) {
            int& v = out.mat[i][j] = 0;
            for (int k=0; k < this->c; ++k) {
                 v = (v+this->mat[i][k]*other.mat[k][j]) % 9901;
            }
        }
    }
}

void pow(int n) {
    matrix out(*this);
    pow(out, n);
    copy(out);
}

void pow(matrix& out, int n) {
    if (n == 0) {
        out.identify();
    } else if ((n%2) == 1) {
        pow(out, n-1);
        matrix a(out);
        multiply(out, a);
    } else {
        pow(out, n/2);
        matrix a(out), b(out);
        a.multiply(out, b);
    }
}

};

int tiling() {
int T[] = {10, 3, 1};
matrix out(3,1,T);
if (N < 4) {
return out.mat[3-N][0];
}
int C[] = {
1, 2, 5,
1, 0, 0,
0, 1, 0
};
matrix w(3,3,C);
matrix m(3,1,T);
w.pow(N-3);
w.multiply(out, m);
return out.mat[0][0];
}

int main(const int argc, const char** argv) {
int T; cin >> T;
while (T--) {
cin >> N;
cout << tiling() << endl;
}
return 0;
}
~~~