class Matrix

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long i64;

class Matrix
{
  private:
    vector < vector < i64 >> matrix;
    i64 _base;
  public:
      Matrix();
      Matrix(vector < i64 > &v, i64 base = 0);
      Matrix(i64 M, i64 N, i64 val = 0, i64 base = 0);
      Matrix(Matrix & m);
    void print();
    i64 getCountRow();
    i64 getCountCol();
    i64 getBase();
    bool setVal(i64 y, i64 x, i64 val);
    i64 getVal(i64 y, i64 x);
    bool setBase(i64 base);
    bool prod(Matrix & b);
    bool prod(Matrix & a, Matrix & b);
    void power(i64 n);
    void sqr();
    void toId();
      Matrix & operator=(Matrix & m);
};

Matrix::Matrix(vector < i64 > &v, i64 base)
{
    matrix.clear();
    _base = base;
    i64 n = round(sqrt(v.size()));
    for (i64 i = 0, k = 0; i < n; ++i)
    {
        vector < i64 > temp;
        for (i64 j = 0; j < n; ++j)
        {
            i64 val = v[k++];
            if (_base != 0)
                val %= _base;
            temp.push_back(val);
            if (k >= v.size())
                k %= v.size();
        }
        matrix.push_back(temp);
    }
}

void Matrix::toId()
{
    i64 countR = getCountRow(), countC = getCountCol();
    for (int i = 0; i < countR; ++i)
        for (int j = 0; j < countC; ++j)
            setVal(i, j, i == j ? 1 : 0);
}

void Matrix::sqr()
{
    Matrix temp = *this;
    prod(temp, temp);
}

void Matrix::power(i64 n)
{
    Matrix t = *this;
    t.toId();
    bool notFinished = true;
    while (notFinished)
    {
        if (n % 2 != 0)
            t.prod(*this);
        n /= 2;
        if (n > 0)
            sqr();
        else
            notFinished = false;
    }
    *this = t;
}

Matrix::Matrix()
{
    vector < i64 > temp(1, 0);
    matrix.clear();
    matrix.push_back(temp);
    _base = 0;
}

i64 Matrix::getVal(i64 y, i64 x)
{
    i64 countR = getCountRow(), countC = getCountCol();
    if (y > countR)
        y %= countR;
    if (x > countC)
        x %= countC;
    return matrix[y][x];
}

Matrix::Matrix(Matrix & m)
{
    matrix = m.matrix;
    _base = m._base;
}

Matrix & Matrix::operator=(Matrix & m)
{
    matrix = m.matrix;
    _base = m._base;
    return *this;
}

bool Matrix::prod(Matrix & b)
{
    Matrix temp = *this;
    return prod(temp, b);
}

bool Matrix::prod(Matrix & a, Matrix & b)
{
    i64 countRowsFromA = a.getCountRow(), countColsFromA = a.getCountCol();
    i64 countRowsFromB = b.getCountRow(), countColsFromB = b.getCountCol();

    bool flag = countColsFromA == countRowsFromB;
    if (!flag)
        return flag;
    matrix.clear();
    _base = a._base;

    for (i64 i = 0; i < countRowsFromA; ++i)
    {
        vector < i64 > temp;
        for (i64 j = 0; j < countColsFromB; ++j)
        {
            i64 temp_val = 0;
            for (i64 k = 0; k < countColsFromA; ++k)
            {

                temp_val += a.getVal(i, k) * b.getVal(k, j);

                if (_base != 0 && (temp_val >= _base || temp_val < 0))
                    temp_val %= _base;
            }
            temp.push_back(temp_val);
        }
        matrix.push_back(temp);
    }
    return flag;
}

i64 Matrix::getCountRow()
{
    return matrix.size();
}

i64 Matrix::getCountCol()
{
    return matrix.at(0).size();
}

i64 Matrix::getBase()
{
    return _base;
}

bool Matrix::setBase(i64 base)
{
    bool flag = _base > base;
    _base = base;
    if (flag)
      for (auto & i:matrix)
          for (auto & j:i)
                j %= _base;
    return flag;
}

Matrix::Matrix(i64 M, i64 N, i64 val, i64 base)
{
    _base = base;
    if (_base != 0)
        val %= _base;
    matrix.clear();
    for (int i = 0; i < M; ++i)
    {
        vector < i64 > temp;
        for (int j = 0; j < N; ++j)
            temp.push_back(val);
        matrix.push_back(temp);
    }
}

void Matrix::print()
{
  for (auto & i:matrix)
    {
      for (auto & j:i)
            cout << j << " ";
        cout << endl;
    }
}

bool Matrix::setVal(i64 y, i64 x, i64 val)
{
    bool flag = y < matrix.size() && x < matrix.at(0).size();
    if (!flag)
        return flag;
    if (_base != 0)
    {
        val %= _base;
    }

    matrix[y][x] = val;
    return flag;
}

int main()
{
    vector < i64 > v ={0, 2, 1, -1};
    Matrix m(v, 5);
    Matrix n = m, k = m;
    for (int i = 0; i <= 100; ++i)
    {
        cout << "step " << i << ":" << endl;
        m = n;
        m.power(i);
        m.print();
    }
    cout << m.getBase() << endl;

    return 0;
}