///
#include <bits/stdc++.h>

typedef long long ll;

int m;
vector<vector<int>> a; ///m*m
vector<vector<int>> bufet;  ///m*m

ll x; ///(x^1)

ll normal_pow_int(int n, ll x) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        ll k = normal_pow_int(n / 2, x);
        return k * k;
    }
    return normal_pow_int(n - 1, x) * x; /// x^(n - 1) * x^1
}

void pow_global_int(int n) {  ///(x^1 -> x^n)
    if (n == 0) {
        x = 1;
        return;
    }
    if (n % 2 == 0) {
        pow_global_int(n / 2); /// x^1 -> x^(n/2)
        x *= x; /// x^(n/2) -> x^n;
        return;
    } else {
        ll k = x; /// k = x^1
        pow_global_int(n - 1); /// x^1 -> x^(n - 1) /// x = 1;
        x *= k;  /// (x^(n - 1) -> x^n) ///x = x * k = 1 * x^1 = x^1
        return;
    }
}


void pow(int n) {
    if (n == 1) {
        return;
    }
    if (n % 2 == 0) {
        pow(n / 2);
        for (int i = 0; i < m; i++){
            for (int j = 0; j < m; ++j){
                bufet[i][j] = a[i][j];
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = 0;
                for (int k = 0; k < m; k++) a[i][j] += a[i][k] * a[k][j];
            }
        }
        return;
    } else {

    }
}