struct Matrix {
    int n, m;
    vector<vector<int>> w;
    Matrix(int n, int m) : n(n), m(m) {
        w.assign(n, vector<int>(m));
    }
    Matrix(vector<vector<int>> t) : w(t), n(t.size()), m(t[0].size()) {}
    friend Matrix operator*(const Matrix& A, const Matrix& B) {
        const auto &a = A.w, b = B.w;
        int n = a.size(), m = b[0].size(), v = b.size();
        vector<vector<int>> c(n, vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < v; k++) {
                    c[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return c;
    }
    friend Matrix qmi(Matrix a, Matrix b, int n) {  // a * (b ^ n)
        while (n) {
            if (n & 1)
                a = a * b;
            b = b * b;
            n >>= 1;
        }
        return a;
    }
};