//
// Created by Beast on 25.03.2023.
// https://codeforces.com/problemset/problem/1117/D

#include <bits/stdc++.h>


using namespace std;
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; ///pow(n - 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] += bufet[i][k] * bufet[k][j];
            }
        }
        return;
    } else {
        for (int i = 0; i < m; i++){ //сохранили a^1
            for (int j = 0; j < m; ++j){
                bufet[i][j] = a[i][j];
            }
        }
        pow(n - 1); /// a^1 -> a^(n - 1)

        for(int i = 0; i < m; ++i){
            for(int j = 0; j < m; ++j){
                for(int k = 0; k < m; ++k) a[i][j] += bufet[i][k] * a[k][j];
        }
    }
}