Templates by Hanggoash

inline int power(int a,int b,int p)
{
	long long ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}

struct Matrix
{
	int n,m;
	int a[maxn][maxn];
	Matrix(){memset(a,0,sizeof a);}
};
Matrix operator *(Matrix a,Matrix b)
{
	Matrix tmp;
	tmp.n=a.n,tmp.m=b.m;
	for(int i=1;i<=a.n;++i)
	{
		for(int j=1;j<=b.m;++j)
		{
			for(int k=1;k<=a.m;++k)
			{
				tmp.a[i][j]=(tmp.a[i][j]+a.a[i][k]*b.a[k][j])%MOD;
			}
		}
	}
	return tmp;
}
Matrix base(int x)
{
	Matrix tmp;
	tmp.n=tmp.m=x;
	for(int i=1;i<=x;++i)tmp.a[i][i]=1;
	return tmp;
}
Matrix power(Matrix a,int b)
{
	Matrix ans=base(a.n);
	while(b)
	{
		if(b&1)ans=ans*a;
		a=a*a;
		b>>=1;
	}
	return ans;
}