封装成结构体，重载了 * 和 ^ 方便矩阵操作。
init() 为初始化矩阵为单位矩阵。
可用于加速递推式计算。

struct matrix
{
    LL mat[20][20];

    void init()
    {
        memset(mat, 0, sizeof(mat));
        for (int i = 0; i <= d; i++) mat[i][i] = 1;
    }

    friend matrix operator * (matrix a, matrix b)
    {
        matrix res;

        for (int i = 0; i <= d; i++)
        {
            for (int j = 0; j <= d; j++)
            {
                res.mat[j][i] = 0;
                for (int k = 0; k <= d; k++)
                {
                    LL val = a.mat[j][k] * b.mat[k][i] % m;
                    res.mat[j][i] = res.mat[j][i] + val % m;
                }
            }
        }

        return res;
    }

    friend matrix operator ^ (matrix base, LL k)
    {
        matrix res;
        res.init();

        while (k)
        {
            if (k & 1) res = res * base;
            base = base * base;
            k >>= 1;
        }

        return res;
    }
};