记录编号	577951	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2013]矩阵游戏	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	1.444 s
提交时间	2022-12-13 16:23:40	内存使用	1.91 MiB

// Problem: P1397 [NOI2013] 矩阵游戏
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1397
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using i64 = long long;

const i64 mod = 1e9 + 7;
const int maxn = 1e6 + 5;
char s[maxn],t[maxn];
i64 a,b,c,d;
int n,m;

struct matrix {
	i64 g[2][2];
	matrix() {
		g[0][0] = g[0][1] = g[1][0] = g[1][1] = 0;
	}
	void init() {
		g[0][0] = g[1][1] = 1;
		return ;
	}
	matrix operator * (const matrix& p)const {
		matrix c;
		for(int k = 0;k < 2;++ k)
			for(int i = 0;i < 2;++ i)
				for(int j = 0;j < 2;++ j)
					(c.g[i][j] += g[i][k] * p.g[k][j]) %= mod;
		return c;
	}
}f,A;

i64 powersum(i64 x,char* y,int len) {
	i64 cur,ans = 1;
	for(int i = 1;i <= len;++ i) {
		for(int k = 1;k <= y[i];++ k)
			(ans *= x) %= mod;
		if(i == len)break ;
		(x *= x) %= mod;
		cur = x;
		(x *= x) %= mod;
		(x *= x) %= mod;
		(x *= cur) %= mod;
	}
	return ans;
}

i64 power(i64 x,i64 y) {
	i64 ans = 1;
	for(;y;y >>= 1) {
		if(y & 1)(ans *= x) %= mod;
		(x *= x) %= mod;
	}
	return ans;
}

void buc(char* s,int& len) {
	for(int i = 1;i <= len;++ i)
		s[i] ^= '0';
	-- s[1];
	for(int i = 1;i < len;++ i) {
		if(s[i] >= 0)break ;
		s[i] += 10;
		s[i + 1] --;
	}
	if(s[len] <= 0)-- len;
	return ;
}

matrix powermatrix(matrix x,char* y,int len) {
	matrix ans,cur;
	ans.init();
	for(int i = 1;i <= len;++ i) {
		for(int k = 1;k <= y[i];++ k)
			ans = ans * x;
		if(i == len)break ;
		x = x * x;
		cur = x;
		x = x * x;
		x = x * x;
		x = x * cur;
	}
	return ans;
}

int main() {
	freopen("matrixb.in","r",stdin);
	freopen("matrixb.out","w",stdout);
	scanf("%s %s %lld %lld %lld %lld",s + 1,t + 1,&a,&b,&c,&d);
	n = strlen(s + 1);
	m = strlen(t + 1);
	std::reverse(s + 1 , s + 1 + n);
	std::reverse(t + 1 , t + 1 + m);
	buc(s , n);
	buc(t , m);
	i64 x;
	if(a > 1)x = (powersum(a , t , m) - 1) * power(a - 1 , mod - 2) % mod;
	else {
		x = 0;
		for(int i = m;i;-- i)
			x = (x * 10 % mod + t[i]) % mod;
	}
	f.g[0][0] = (powersum(a , t , m) + x * b % mod) % mod;
	f.g[0][1] = 1;
	A.g[0][0] = powersum(a , t , m) * c % mod;
	A.g[0][1] = 0;
	A.g[1][0] = (powersum(a , t , m) * d % mod + x * b % mod) % mod;
	A.g[1][1] = 1;
	printf("%lld",(f * powermatrix(A , s , n)).g[0][0]);
	return 0;
}