模板

struct Matrix {
    static const int MAXN = 100;
    static const int MOD = 1e9 + 7;
    int n, a[MAXN + 5][MAXN + 5];

    Matrix(int _n = 0) {n = _n;}

    int add(const int &a, const int &b)const {
        int c = a + b;
        if(c >= MOD)
            c -= MOD;
        return c;
    }

    int sub(const int &a, const int &b)const {
        int c = a - b;
        if(c < 0)
            c += MOD;
        return c;
    }

    int mul(const int &a, const int &b)const {
        ll c = 1ll * a * b;
        if(c >= MOD)
            c %= MOD;
        return (int)c;
    }

    void Init(int _n, const int _a[MAXN + 5][MAXN + 5]) {
        n = _n;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j)
                a[i][j] = _a[i][j];
        }
    }

    void ZERO(int _n) {
        n = _n;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j)
                a[i][j] = 0;
        }
    }


    void ONE(int _n) {
        n = _n;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j)
                a[i][j] = (i == j);
        }
    }

    Matrix operator+(const Matrix& m)const {
        Matrix res(n);
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j)
                res.a[i][j] = add(a[i][j], m.a[i][j]);
        }
        return res;
    }

    Matrix operator-(const Matrix& m)const {
        Matrix res(n);
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j)
                res.a[i][j] = sub(a[i][j], m.a[i][j]);
        }
        return res;
    }

    Matrix operator*(const Matrix& m)const {
        Matrix res;
        res.ZERO(n);
        for(int k = 1; k <= n; ++k) {
            for(int i = 1; i <= n; ++i) {
                for(int j = 1; j <= n; ++j)
                    res.a[i][j] = add(res.a[i][j], mul(a[i][k], m.a[k][j]));
            }
        }
        return res;
    }

    Matrix pow(ll k)const {
        Matrix x, res;
        x.Init(n, a);
        res.ONE(n);
        while(k) {
            if(k & 1)
                res = res * x;
            x = x * x;
            k >>= 1;
        }
        return res;
    }

    void Show(string name = "") {
        //cout << "Matrix " << name << " = 
";
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j)
                printf("%d%c", a[i][j], " 
"[j == n]);
        }
    }
};