#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y,m;
vector<vector<int> > mul(vector<vector<int> > a,vector<vector<int> > b){
	vector<vector<int> > c(a.size(),vector<int>(b[0].size()));
	for(int i=0;i<a.size();i++){
		for(int j=0;j<b[0].size();j++){
			for(int k=0;k<a[0].size();k++){
				c[i][j]+=a[i][k]*b[k][j];
				c[i][j]%=m;
			}
		}
	}
	return c;
}
vector<vector<int> > qp(vector<vector<int> > a,int n){
	vector<vector<int> > b(a[0].size(),vector<int>(a.size()));
	for(int i=0;i<b.size();i++){
		b[i][i]=1;
	}
	while(n){
		if(n%2)b=mul(a,b);
		a=mul(a,a);
		n/=2;
	}
	return b;
}
void exgcd(int a,int b){
	if(b==0){
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b);
	int t=x;
	x=y;
	y=t-a/b*y;
}
int ny(int a,int b){
	exgcd(b/__gcd(m,b),m);
	int ans=(a*(x%m+m)%m)%m;
	x=y=0;
	return ans;
}
signed main(){
	
}