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);
    Matrix& prod(Matrix& b);
    void 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(){
    cout<<"raz "<<getBase()<<endl;
    prod(*this, *this);
    cout<<"dva "<<getBase()<<endl;
}

void Matrix::power(i64 n){
    Matrix t = *this; t.toId();
    bool notFinished = true;
    while ( notFinished ) {
        if ( n % 2 != 0 ) t = 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;
}

Matrix& Matrix::prod(Matrix& b){
    i64 countR = getCountRow(), countC = b.getCountCol(), d = getCountCol(), base = getBase();
    Matrix temp(countR, countC, 0, base);
    cout<<"var temp base: "<<temp.getBase()<<endl;
    cout<<base<<endl;
    for ( i64 i = 0; i < countR; ++i )
        for ( i64 j = 0; j < countC; ++j ){
            i64 temp_val = 0;
            for (i64 k = 0; k < d; ++k){
                temp_val += getVal(i, k) * b.getVal(k, j);
                if ( base != 0 && temp_val >= base ) temp_val %= base;
            }
            temp.setVal(i, j, temp_val);
        }
    cout<<"var temp base: "<<temp.getBase()<<endl;
    return temp;
}

void Matrix::prod(Matrix& a, Matrix& b){
    cout<<"var a: base = "<<a.getBase()<<endl;
    a = a.prod(b);
    cout<<"var a: base = "<<a.getBase()<<endl;
    a.print();
    matrix = a.matrix;
    _base = a._base;
}

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);
    cout<<"step 1:"<<endl;
    m.print();
    m.prod(m,m);
    cout<<"step 2:"<<endl;
    m.print();
    return 0;
}