【模板】矩阵运算

struct Matrix
{
    int n, m, rec[N][N];    // 矩阵的长，宽和二维数组
    
    Matrix(int _n, int _m) { n = _n, m = _m, memset(rec, 0, sizeof rec); }    // 初始化函数
    void reset() { n = 0, m = 0, memset(rec, 0, sizeof rec); }
    
    int* operator [] (int i) { return rec[i]; }    // 重载数组
    const int* operator [] (int i) const { return rec[i]; }    // 重载数组

    friend Matrix operator * (const Matrix &a, const Matrix &b)    // 矩阵乘法
    {
        Matrix res(a.n, b.m);
        for (int k = 0; k < a.m; k ++)
            for (int i = 0; i < res.n; i ++)
                for (int j = 0; j < res.m; j ++)
                    res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod;
        return res;
    }
    
    friend Matrix operator ^ (Matrix A, int k)  // 矩阵快速幂
    {
        Matrix res(A.n, A.m);
        for (int i = 0; i < res.n; i ++) res[i][i] = 1;
        while (k)
        {
            if (k & 1) res = res * A;
            A = A * A, k >>= 1;
        }
        return res;
    }
};

struct Matrix
{
    int n, m, rec[N][N];
    
    Matrix(int _n, int _m) { n = _n, m = _m, memset(rec, 0, sizeof rec); }
    void reset() { n = 0, m = 0, memset(rec, 0, sizeof rec); }
    
    int* operator [] (int i) { return rec[i]; }
    const int* operator [] (int i) const { return rec[i]; }

    friend Matrix operator * (const Matrix &a, const Matrix &b)
    {
        Matrix res(a.n, b.m);
        for (int k = 0; k < a.m; k ++)
            for (int i = 0; i < res.n; i ++)
                for (int j = 0; j < res.m; j ++)
                    res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod;
        return res;
    }
    
    friend Matrix operator ^ (Matrix A, int k)
    {
        Matrix res(A.n, A.m);
        for (int i = 0; i < res.n; i ++) res[i][i] = 1;
        while (k)
        {
            if (k & 1) res = res * A;
            A = A * A, k >>= 1;
        }
        return res;
    }
};