LGTB 有一个非常大的数，并且他想对它进行Q 次操作
每次操作是把这个大数中的某种数字全部替换成一个数字串
他想知道Q 次操作之后得到的数对1000000007(109 + 7) 取模的结果，请输出给他
输入
输入第一行代表一个串S 代表初始的数
接下来一行有一个数字Q 代表操作次数
接下来Q 行，每行一个形如a->b1b2b3…bk 的串，代表将a 变成b1b2b3…bk
对于40% 的数据，1|S|<=1000，1<=Q<=10
对于100% 的数据，1<=|S|<=10^5，1<=Q<=10^5，询问中b 串的总长度不超过105
注意b 串可以为空
输出
输出包含一个数字，代表LGTB 想要的结果
样例
样例输入样例输出
123123
1
2->00
10031003
样例输入样例输出
222
2
2->0
0->7
777
最终答案肯定是由每个原串里的数字变成一个区间得到的
所以我们用dp[i][j]代表i这个数字从第j个询问开始进行到最后得到的数%1e9+7答案是多少
再用L[i][j]代表i这个数字从第j个询问开始进行到最后得到的数的长度是多少
那么对于原串中的每个数，对于答案的贡献就是dp[i][q] * pow(10,之后所有数的长度和)
dp从后往前转移即可，唯一需要注意的就是长度也要取模，因为是指数，根据费马小定理应该对1e9+6取模
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long lol;
lol Mod=;
string s,Q[];
lol ans,num[],f[][],LL,L[][];
lol qpow(lol x,lol y)
{
lol res=;
while (y)
{
if (y&) res=res*x%Mod;
x=x*x%Mod;
y=y/;
}
return res;
}
int main()
{int i,q,j,k;
cin>>s;
cin>>q;
for (i=;i<=q;i++)
{
cin>>Q[i];
num[i]=Q[i][]-'';
int len=Q[i].size();
Q[i]=Q[i].substr(,len-);
}
for (i=;i<=;i++)
f[i][q+]=i,L[i][q+]=;
for (i=q;i>=;i--)
{
for (j=;j<;j++)
{
if (num[i]!=j)
{
f[j][i]=f[j][i+];
L[j][i]=L[j][i+];
continue;
}
L[j][i]=;
f[j][i]=;
for (k=Q[i].size()-;k>=;k--)
{
f[j][i]+=f[Q[i][k]-''][i+]*qpow(,L[j][i])%Mod;
f[j][i]%=Mod;
L[j][i]+=L[Q[i][k]-''][i+];
L[j][i]%=Mod-;
}
}
}
int len=s.size();
LL=;ans=;
for (i=len-;i>=;i--)
{
ans+=f[s[i]-''][]*qpow(,LL)%Mod;
ans%=Mod;
LL+=L[s[i]-''][];
LL%=Mod-;
}
cout<<ans;
}