//矩阵快速幂模板
#include<iostream>
#include<iomanip>
#include<cstring>
#include<stdio.h>
#include<map>
#include<cmath>
#include<algorithm>
#include<vector>
#include<stack>
#include<fstream>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define fab(i,a,b) for(int i=(a);i<=(b);i++)
#define fba(i,b,a) for(int i=(b);i>=(a);i--)
#define MP make_pair
#define PB push_back

using namespace std;
const int N=15;
struct ma{
    int row,col;
    int a[N][N];
    ma operator*(const ma& other){
        ma res;
        res.row=row;
        res.col=other.col;
        rep(i,row){
            rep(j,other.col){
                res.a[i][j]=0;
                rep(k,col){
                    res.a[i][j]+=a[i][k]*other.a[k][j];
                }
            }
        }
        return res;
    }
};
ma pow_ma(const ma& x,int n){
    ma base=x,res;
    rep(i,x.row){
        rep(j,x.col){
            if(i==j)res.a[i][j]=1;
            else res.a[i][j]=0;
        }
    }
    while(n){
        if(n&1)res=res*base;
        base=base*base;
        n>>=1;
    }
}