#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int K = 2;
template<class T>
struct Matrix {
    int row, col;
    T a[K][K];
    Matrix(int x = 0, int y = 0) {
        memset(a, 0, sizeof a);
        row = x, col = y;
    }
    void identity() {
        memset(a, 0, sizeof a);
        //row = x, col = y;
        for (int i = 0; i < row; i++) a[i][i] = 1;
    }
    void input() {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) cin >> a[i][j];
        }
    }
    void print() {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) cout << a[i][j] << ' '; cout << '\n';
        }
    }
    Matrix& operator=(const Matrix& b) {
        row = b.row, col = b.col;
        for (int i = 0; i < b.row; i++) {
            for (int j = 0; j < b.col; j++) {
                a[i][j] = b.a[i][j];
            }
        }
        return *this;
    }
    bool operator!=(const Matrix& b) {
        if (row != b.row || col != b.col) return true;
        for (int i = 0; i < b.row; i++) {
            for (int j = 0; j < b.col; j++) {
                if (a[i][j] != b.a[i][j]) return true;
            }
        }
        return false;
    }
    Matrix operator+(const Matrix& b) {
        Matrix res(row, b.col);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                res.a[i][j] = a[i][j] + b.a[i][j];
            }
        }
        return res;
    }
    Matrix operator-(const Matrix& b) {
        Matrix res(row, b.col);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                res.a[i][j] = a[i][j] - b.a[i][j];
            }
        }
        return res;
    }
    Matrix operator*(const Matrix& b) {
        Matrix res(row, b.col);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < b.col; j++) {
                for (int k = 0; k < col; k++) {
                    res.a[i][j] += a[i][k] * b.a[k][j];
                }
            }
        }
        return res;
    }
    Matrix Power(int k) {
        Matrix res(row, col);
        Matrix x(row, col);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) x.a[i][j] = a[i][j];
        }
        res.identity();
        while (k) {
            if (k & 1)res = res * x;
            k >>= 1;
            x = x * x;
        }
        return res;
    }
    Matrix transpose() {
        Matrix res(col, row);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) res.a[j][a.row - i - 1] = a[i][j];
        }
        return res;
    }
};