fork download
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. #define MOD 1000000007
  4. using namespace std;
  5. struct fog{
  6. long long int x;
  7. long long int size;
  8. }dp[10];
  9. long long int p[1000000];
  10. long long int power(long long int n){
  11. if(p[n]!=-1)
  12. return p[n];
  13. if(n==1)
  14. return 10;
  15. if(n==0)
  16. return 1;
  17. if(n%2==0){
  18. if(n<1000000){
  19. if(p[n/2]!=-1)
  20. return p[n]=(p[n/2]*p[n/2])%MOD;
  21. p[n]=(power(n/2)*power(n/2))%MOD;}
  22. else
  23. return (power(n/2)*power(n/2))%MOD;
  24.  
  25. }
  26. else{if(n<1000000){
  27. if(p[(n-1)/2]!=-1)
  28. return p[n]=(10*((p[(n-1)/2]*p[(n-1)/2])%MOD))%MOD;
  29. p[n]=(10*((power((n-1)/2)*power((n-1)/2))%MOD))%MOD;
  30. }
  31. else{
  32. return (10*((power((n-1)/2)*power((n-1)/2))%MOD))%MOD;}
  33. }
  34. return p[n];
  35.  
  36.  
  37. }
  38. int main()
  39. { for(int i=0;i<10;++i)
  40. dp[i].x=i,dp[i].size=1;
  41. for(int i=0;i<1000000;++i)
  42. p[i]=-1;
  43. string s;
  44. cin >> s;
  45. int q;
  46. cin >> q;
  47.  
  48. string A[q+1];
  49. for(int i=1;i<=q;++i)
  50. cin >> A[i];
  51. for(int i=q;i>0;--i){
  52. int a=A[i][0]-'0';
  53. long long int b=0;
  54. long long int size=0;
  55. if(A[i].size()<=3){
  56. dp[a].x=0;
  57. dp[a].size=0;
  58. }
  59. else{long long int c=A[i][3]-'0';
  60. b=dp[c].x;
  61. size+=dp[c].size;
  62. for(int j=4;j<A[i].size();++j){
  63. c=A[i][j]-'0';
  64. b=(((power(dp[A[i][j]-'0'].size)*b)%MOD)+dp[A[i][j]-'0'].x)%MOD;
  65. size+=dp[c].size;
  66.  
  67. }
  68. dp[a].x=b;
  69. dp[a].size=size;
  70. }
  71.  
  72.  
  73. }
  74. long long int ans=0;
  75. ans=dp[s[0]-'0'].x;
  76. for(int i=1;i<s.size();++i){
  77. ans=(((power((dp[s[i]-'0']).size)*ans)%MOD)+dp[s[i]-'0'].x)%MOD;
  78. }
  79.  
  80. cout << ans << endl;
  81. return 0;
  82.  
  83. }
Success #stdin #stdout 0s 11048KB
stdin
123123
1
2->00
stdout
10031003