#include <bits/stdc++.h>
using namespace std;
const int P=1e9+7; 
struct Matrix{
	int R,C;
	vector<vector<long long>> a;
	Matrix()
	{
		R=C=0;
	}
	Matrix(int r,int c)
	{
		R=r,C=c;
		a=vector<vector<long long>>(r,vector<long long>(c));
	}
	Matrix(vector<vector<long long>> v)
	{
		R=v.size();
		C=v[0].size();
		a=v; 
	}
	void print()
	{
		for(auto v:a)
		{
			for(auto x:v)
			{
				cout <<(x+P)%P<<" ";
			}
			cout <<'\n';
		}
	}
};
Matrix operator * (const Matrix &A,const Matrix &B)
{
	Matrix D(A.R , B.C);
	for(int i=0;i<D.R;i++)
	{
		for(int j=0;j<D.C;j++)
		{
			for(int k=0;k<B.R;k++)
			{
				D.a[i][j]=(D.a[i][j] + A.a[i][k] * B.a[k][j])%P;
			}
		}
	}
	return D;
}
Matrix operator ^ (const Matrix &A,long long n)
{
	Matrix X=A;
	Matrix ans(A.R,A.C);
	for(int i=0;i<A.R;i++) ans.a[i][i]=1;
	while(n)
	{
		if(n&1) ans=ans*X;
		X=X*X;
		n>>=1; 
	}
	return ans;
}
int main()
{
	
	return 0;
}