记录编号	577949	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2013]矩阵游戏	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	1.674 s
提交时间	2022-12-13 15:14:35	内存使用	1.83 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
struct sdf{
	ll p[2][2];
	sdf(){
		for (int i=0;i<=1;i++){
			for (int j=0;j<=1;j++)p[i][j]=0;
		}
	}
	sdf operator*(const sdf&x){
		sdf tmp;
		for (int i=0;i<=1;i++){
			for (int j=0;j<=1;j++){
				for (int k=0;k<=1;k++){
					tmp.p[i][j]=(tmp.p[i][j]+p[i][k]*x.p[k][j]%mod)%mod;
				}
			}
		}
		return tmp;
	}
}A[12],B,C,D[12],E,bs,tmp; 
ll a,b,c,d;
string n,m;
int nl,ml;
sdf pw(sdf x,int y){
	if (!y)return bs;
	if (y&1)return pw(x,y-1)*x;
	sdf P=pw(x,y/2);return P*P;
}
void fst1(int pt){
	if (pt>=nl)return ;
	C=pw(C,10);
	C=C*A[n[pt]-'0'];
	fst1(pt+1);
}
void fst2(int pt){
	if (pt>=ml)return ;
	E=pw(E,10);
	E=E*D[m[pt]-'0'];
	fst2(pt+1);
}
int main(){
	freopen ("matrixb.in","r",stdin);
	freopen ("matrixb.out","w",stdout);
	cin>>m>>n;
	scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
	ml=m.length(),nl=n.length();
	for (int i=ml-1;i>=0;i--){
		if (m[i]=='0')m[i]='9';
		else{
			m[i]--;break;
		}
	}
	for (int i=nl-1;i>=0;i--){
		if (n[i]=='0')n[i]='9';
		else{
			n[i]--;break;
		}
	}
	A[1].p[0][0]=a;A[1].p[0][1]=b;A[1].p[1][0]=0;A[1].p[1][1]=1;
	B.p[0][0]=c;B.p[0][1]=d;B.p[1][0]=0;B.p[1][1]=1;
	bs.p[0][0]=bs.p[1][1]=1;bs.p[0][1]=bs.p[1][0]=0;
	A[0]=D[0]=C=E=bs;
	for (int i=2;i<=9;i++)A[i]=A[i-1]*A[1];
	if (n[0]!='0')fst1(0);
	else fst1(1);
	D[1]=C*B;
	for (int i=2;i<=9;i++)D[i]=D[i-1]*D[1];
	if (m[0]!='0')fst2(0);
	else fst2(1);
	E=E*C;
	ll ans=(E.p[0][0]+E.p[0][1])%mod;
	printf("%lld\n",ans);
	return 0;
}