- /*
- 感觉做这题只要对矩阵乘法理解的稍微一点就能做出来
- 对于每一行构造一个矩阵
- A = a 1
- 0 b
- 列与列之间的矩阵为
- B = c 1
- 0 d
- 最终答案为
- $A^{n - 1}B A^{n - 1}B$
- 把$A^{n-1}B$看成一项进行快速幂即可
- maya把数据范围看漏了1e6个0。。。。。。。
- 好像把快速幂换成十进制快速幂就行了
- */
- #include<bits/stdc++.h>
- #define LL long long
- #define int long long
- const int MAXN = 1e6 + 10, mod = 1e9 + 7, L = 2;
- using namespace std;
- char t1[MAXN], t2[MAXN];
- int N[MAXN], M[MAXN], a, b, c, d, n, m;
- int Mod(int x, int y) {
- if(1ll * x * y > mod) return 1ll * x * y % mod;
- else return 1ll * x * y;
- }
- int add(int x, int y) {
- if(x + y > mod) return x + y - mod;
- else return x + y;
- }
- struct Matrix {
- int m[4][4];
- Matrix() {
- memset(m, 0, sizeof(m));
- }
- Matrix operator * (const Matrix &rhs) const {
- Matrix ans;
- /*for(int k = 1; k <= L; k++)
- for(int i = 1; i <= L; i++)
- for(int j = 1; j <= L; j++)
- (ans.m[i][j] += 1ll * m[i][k] * rhs.m[k][j] % mod) %= mod;*/
- ans.m[1][1] = add(Mod(m[1][1], rhs.m[1][1]), Mod(m[1][2], rhs.m[2][1]));
- ans.m[1][2] = add(Mod(m[1][1], rhs.m[1][2]), Mod(m[1][2], rhs.m[2][2]));
- ans.m[2][1] = add(Mod(m[2][1], rhs.m[1][1]), Mod(m[2][2], rhs.m[2][1]));
- ans.m[2][2] = add(Mod(m[2][1], rhs.m[1][2]), Mod(m[2][2], rhs.m[2][2]));
- return ans;
- }
- };
- Matrix fp(Matrix a, int *p, int len) {
- Matrix base;
- for(int i = 1; i <= 3; i++) base.m[i][i] = 1;
- for(int i = len; i >= 1; i--) {
- for(int j = 1; j <= p[i]; j++) base = base * a;
- Matrix tmp = a;
- a = a * a; a = a * a; a = a * a; a = a * tmp * tmp;
- }
- return base;
- }
- int trans(char *s, int l, int *to) {
- for(int i = 1; i <= l; i++) to[i] = s[i] - '0';
- to[l]--;
- for(int i = l; i >= 1; i--)
- if(to[i] < 0) to[i - 1] += to[i], to[i] = 10 + to[i];
- else break;
- return l;
- }
- main() {
- // freopen("a.in", "r", stdin);
- scanf("%s%s%d%d%d%d", t1 + 1, t2 + 1, &a, &b, &c, &d);
- n = strlen(t1 + 1); m = strlen(t2 + 1);
- n = trans(t1, n, N); m = trans(t2, m, M);
- Matrix x, y;
- x.m[1][1] = a; x.m[1][2] = b;
- x.m[2][1] = 0; x.m[2][2] = 1;
- y.m[1][1] = c; y.m[1][2] = d;
- y.m[2][1] = 0; y.m[2][2] = 1;
- Matrix debug = fp(x, M, m) ;
- debug = debug * y;
- Matrix ans = fp(debug, N, n);
- ans = ans * fp(x, M, m);
- cout << (ans.m[1][1] + ans.m[1][2]) % mod;
- }