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取模

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 typedef long long lol; 8 lol Mod=1000000007; 9 string s,Q[100005];10 lol ans,num[100005],f[10][100005],LL,L[10][100005];11 lol qpow(lol x,lol y)12 {13   lol res=1;14   while (y)15     {16       if (y&1) res=res*x%Mod;17       x=x*x%Mod;18       y=y/2;19     }20   return res;21 }22 int main()23 {
   int i,q,j,k;24   cin>>s;25   cin>>q;26   for (i=1;i<=q;i++)27     {28       cin>>Q[i];29       num[i]=Q[i][0]-'0';30       int len=Q[i].size();31       Q[i]=Q[i].substr(3,len-3);32     }33   for (i=0;i<=9;i++)34     f[i][q+1]=i,L[i][q+1]=1;35   for (i=q;i>=1;i--)36     {37       for (j=0;j<10;j++)38     {39       if (num[i]!=j)40         {41           f[j][i]=f[j][i+1];42           L[j][i]=L[j][i+1];43           continue;44         }45       L[j][i]=0;46       f[j][i]=0;47       for (k=Q[i].size()-1;k>=0;k--)48         {49           f[j][i]+=f[Q[i][k]-'0'][i+1]*qpow(10,L[j][i])%Mod;50           f[j][i]%=Mod;51           L[j][i]+=L[Q[i][k]-'0'][i+1];52           L[j][i]%=Mod-1;53         }54     }55     }56   int len=s.size();57   LL=0;ans=0;58   for (i=len-1;i>=0;i--)59     {60       ans+=f[s[i]-'0'][1]*qpow(10,LL)%Mod;61       ans%=Mod;62       LL+=L[s[i]-'0'][1];63       LL%=Mod-1;64     }65   cout<