首先，构造出从f[][i]->f[][i+1]的转移矩阵a，和从f[i][m]->f[i+1][1]的转移矩阵b，
那么从f[1][1]转移到f[n][m]就是init*(a^(m-1)*b)^(n-1)*(a^(m-1))。
然后用用十进制快速幂（因为输入用的是10进制，这样就避免了高精度除法）。
第一次写十进制快速幂，大概的思想是维护当前位是1～9的要乘的矩阵，然后再通过这9个矩阵自己转移。
/**************************************************************
Problem: 3240
User: idy002
Language: C++
Result: Accepted
Time:5352 ms
Memory:2764 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#define N 1000010
#define Mod 1000000007
using namespace std; typedef long long dnt;
struct Matrix {
dnt v[][];
void make_unit() {
for( int i=; i<; i++ )
for( int j=; j<; j++ )
v[i][j] = (i==j);
}
inline const dnt* operator[]( int i ) const { return v[i]; }
Matrix(){}
Matrix( int aa, int ab, int ba, int bb ) {
v[][] = aa, v[][] = ab, v[][] = ba, v[][] = bb;
}
Matrix operator*( const Matrix &b ) const {
const Matrix &a = *this;
return Matrix( , (b[][]+a[][]*b[][])%Mod,
, a[][]*b[][]%Mod );
}
Matrix operator^( const char *b ) const {
Matrix rt, q[]; q[] = *this;
for( int i=; i<=; i++ )
q[i] = q[i-]*q[]; rt.make_unit();
for( int i=; b[i]; i++ ) {
if( b[i]-'' ) rt = rt*q[b[i]-''];
q[] = q[]*q[];
for( int j=; j<=; j++ )
q[j] = q[j-]*q[];
}
return rt;
}
}; char sn[N], sm[N];
int ln, lm;
int a, b, c, d;
Matrix ma, mb, ans; void subone( char s[] ) {
int i = ;
s[i]--;
while( s[i]<'' ) {
s[i] += ;
s[i+]--;
i++;
}
}
int main() {
scanf( "%s%s%d%d%d%d", sn, sm, &a, &b, &c, &d );
ln = strlen(sn), lm = strlen(sm);
reverse( sn, sn+ln );
reverse( sm, sm+lm );
subone(sn), subone(sm);
ma = Matrix(,b,,a)^sm;
mb = Matrix(,d,,c);
ans = ((ma*mb)^sn)*ma;
printf( "%lld\n", (ans[][]+ans[][]) % Mod );
}