c++ - 行列累乗における整数オーバーフロー

Question

私は、行列の累乗が必要ないくつかのシーケンスを生成しようとしています。私のコードは、小さなケースに対して正しい値を生成します.2つの異なるシーケンスに使用している2つの異なるマトリックスを以下に示しました.

マトリックス1

[2  1 -2 -1]
[1  0  0  0]
[0  1  0  0]
[0  0  1  0]  

マトリックス2

[4 1]
[-4 0]

以前、行列に負でない値を使用して累乗を試みたことがあり、目的の結果が得られていました。

結果の大きな値に対応するために、MOD=1000000007 を使用しています。

私が理解している限り、マトリックス内の値の1つがMODによって減少し、他の値が減少しない場合に問題が発生し、最終結果が間違っています.また、負の値も大きくなっているので、私もそうではありませんそれらをどうするかを確認してください。私の最終的な答えは、多くの値に対して否定的です。

この問題に関するリンク/リソース/ヘルプを高く評価します。
コードは次のとおりです。フィボナッチ積を生成します。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <list>
#include <map>
#include<conio.h>
#include <cassert>
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define fill(x,y) memset(x,y,sizeof(x))
#define Size(x) (int(x.size()))
#define FOR(k,a,b) for(typeof(a) k=(a); k < (b); ++k)
typedef long long ll;
using namespace std;
#define dim 4


struct matrix
{
    int a[dim][dim];
};

#define MOD 1000000007

matrix mul(matrix x, matrix y)
{
    matrix res;
    FOR(a, 0, dim) FOR(b, 0, dim) res.a[a][b] = 0;
    FOR(a, 0, dim) FOR(b, 0, dim) FOR(c, 0, dim)
    {
        res.a[a][c] += (x.a[a][b] * ll(y.a[b][c])) % MOD;
        res.a[a][c] %= MOD;
    }
    return res;
}

matrix power(matrix m, int n)
{
    if (n == 1) return m;
    matrix u = mul(m, m);
    u = power(u, n / 2);
    if (n & 1) u = mul(u, m);
    return u;
}

matrix M, C, D, RP, A;

int main()
{
    FOR(a, 0, dim) FOR(b, 0, dim) M.a[a][b] = 0;
    M.a[0][0] = 2;
    M.a[1][0] = 1;
    M.a[2][0] = -2;
    M.a[3][0] = -1;
    M.a[0][1] = M.a[1][2] = M.a[2][3] = 1;
    C.a[0][0] = 96;
    C.a[0][1] = 44;
    C.a[0][2] = 18;
    C.a[0][3] = 5;
    int nt;
    scanf("%d", & nt);
    while (nt--)
    {
        int n;
        scanf("%d", & n);
        if (n <= 5)
        {
            if (n == 5) printf("96\n");
            if (n == 4) printf("44\n");
            if (n == 2) printf("5\n");
            if (n == 3) printf("18\n");
            if (n == 1) printf("2\n");
            continue;
        }
        if (n > 5)
        {
            int rs = n - 5;
            RP = power(M, rs);
            A = mul(C, RP);
            printf("%d\n", A.a[0][0]);
        }
    }
    getch();
    return 0;
}