### Матрицы с оптимизированным умножением

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define long ll
#define all(x) begin(x), end(x)

using Scalar = long;

struct Matrix {
    int n, m;
    vector<Scalar> data;

    Matrix() : n(0), m(0), data(0) {}

    Matrix(int x, int y) :
        n(x),
        m(y),
        data(x * y, 0) {}

    Scalar &operator()(int i, int j) {
        //assert(0 <= i && i < n);
        //assert(0 <= j && j < m);
        return data[i * n + j];
    }

    Scalar operator()(int i, int j) const {
        //assert(0 <= i && i < n);
        //assert(0 <= j && j < m);
        return data[i * n + j];
    }
};

Matrix identity(int n) {
    Matrix a(n, n);
    for (int i = 0; i < n; ++i) {
        a(i, i) = 1;
    }
    return a;
}

Matrix transpose(const Matrix &a) {
    int n = a.n, m = a.m;
    Matrix b(m, n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            b(i, j) = a(j, i);
        }
    }
    return b;
}

Matrix operator*(const Matrix &a, Matrix b) {
    assert(a.m == b.n);
    int n = a.n, m = b.m, k = a.m;
    b = transpose(b);
    Matrix c(n, m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int t = 0; t < k; ++t) {
                c(i, j) += a(i, t) * b(j, t);
            }
        }
    }
    return c;
}

Matrix fast_power(Matrix a, int p) {
    assert(a.n == a.m);
    int n = a.n;
    Matrix x = identity(n);
    for (; p > 0; p >>= 1) {
        if (p & 1) {
            x = x * a;
        }
        a = a * a;
    }
    return x;
}

ostream &operator<<(ostream &out, const Matrix &a) {
    for (int i = 0; i < a.n; ++i) {
        for (int j = 0; j < a.m; ++j) {
            out << a(i, j) << '\t';
        }
        out << '\n';
    }
    return out;
}


int main() {
#ifdef LC
    //assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}