文件详细信息

下载本文件

本文件的大小为 1438 字节。

#include<cstdio>
#include<cstring>
typedef long long ll;
const int maxlen=1000005;
const ll P=1000000007;
char n[maxlen],m[maxlen];
int _n,_m,a,b,c,d;
struct Matrix{
	ll a[2][2];
	Matrix(){
		a[0][0]=a[0][1]=a[1][0]=a[1][1]=0;
	}
}I,init,trans_1,trans_2;
Matrix operator*(const Matrix a,const Matrix b){
	Matrix res;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)
				res.a[i][k]=(res.a[i][k]+a.a[i][j]*b.a[j][k])%P;
	return res;
}
Matrix qpow(const Matrix a,int x){
	if(x==1)return a;
	if(x==2)return a*a;
	Matrix b=a*a;
	if(x==3)return a*b;
	if(x==4)return b*b;
	Matrix c=b*b;
	if(x==5)return a*c;
	if(x==6)return b*c;
	if(x==7)return a*b*c;
	if(x==8)return c*c;
	if(x==9)return a*c*c;
	if(x==10)return b*c*c;
}
Matrix qpow(Matrix a,char*num,int len){
	Matrix res=I;
	while(len){
		if(num[len]!='0')res=res*qpow(a,num[len]-'0');
		a=qpow(a,10);
		len--;
	}
	return res;
}
int main(){
	scanf("%s%s%d%d%d%d",n+1,m+1,&a,&b,&c,&d);
	_n=strlen(n+1);
	_m=strlen(m+1);
	for(int i=_n;i>=1;i--)
		if(n[i]>'0'){
			n[i]--;
			break;
		}else n[i]='9';
	for(int j=_m;j>=1;j--)
		if(m[j]>'0'){
			m[j]--;
			break;
		}else m[j]='9';
	I.a[0][0]=I.a[1][1]=1;
	init.a[0][0]=init.a[0][1]=1;
	trans_1.a[0][0]=a;
	trans_1.a[1][0]=b;
	trans_1.a[1][1]=1;
	trans_2.a[0][0]=c;
	trans_2.a[1][0]=d;
	trans_2.a[1][1]=1;
	Matrix tmp=qpow(trans_1,m,_m);
	Matrix ans=init*qpow(tmp*trans_2,n,_n)*tmp;
	printf("%lld\n",ans.a[0][0]);
	return 0;
}