you're given the initial string s and the integer x. What is the length of s when the procedure stops? Since this value may be very large, only find it modulo 109+

The first line of input contains a single integer t$t$ (1≤t≤1000$1\le t\le 1000$) denoting the number of test cases. The next lines contain descriptions of the test cases.

The first line of each test case contains a single integer x$x$ (1≤x≤106$1\le x\le {10}^6$). The second line of each test case consists of the initial string s$s$ (1≤|s|≤500$1\le |s|\le 500$). It is guaranteed, that s$s$ consists of the characters "1", "2", "3".

It is guaranteed that the sum of x$x$ in a single file is at most 106${10}^6$. It is guaranteed that in each test case before the procedure will stop it will be true that ℓ≤|s|$\ell \le |s|$ at any time.

Output:

For each test case, output a single line containing a single integer denoting the answer for that test case modulo 

109+7${10}^9+7$.

1. #include<bits/stdc++.h>
2. #define M 1000000007
3. using namespace std;
4. int main()
5. {
6. int t;
7. cin>>t;
8. while(t--)
9. {
10. long long int x;
11. string s,c,tmp="";
12. cin>>x;
13. cin>>s;
14. long long int l=1;
15. long long int a[x+1];
16. a[0]=s.size()%M;
17. for(long long int i=1;i<=x;++i)
18. {
19. a[i]=0;
20. for(int j=0;j<(s[i-1]-'0');++j)
21. a[i]=(a[i]+a[i-1]-i)%M;
22. a[i]+=i;
23. if(s.size()<=x)
24. {
26. tmp=s.substr(0,i);
27. c=s.substr(i,s.size()-i);
28. int l=s[i-1]-'0';
29. while(l--)
30. {
31. tmp+=c;
32. if(tmp.size()>=x)
33. break;
34. }
35. s=tmp;
36. }
37. }
38. cout<<a[x]%M<<endl;
39. }
40. return 0;
41. }

Another trick for time limit:--

1. #include<bits/stdc++.h>
2. #define M 1000000007
3. using namespace std;
4. int main()
5. {
6. int t;
7. cin>>t;
8. while(t--)
9. {
10. long long int x;
11. string _s,c,tmp="";
12. cin>>x;
13. cin>>(_s);
14. unsigned long long int ls=(_s).size();
15. vector <char> s(_s.begin(),_s.end());
16. for (int i = 1; i <= x; ++i)
17. {
18. int v = s[i - 1] - '1';
19. if (s.size() < x)
20. {
21. vector<char> sub(s.begin() + i, s.end());
22. for (int it = 0; it < v; it++) s.insert(s.end(), sub.begin(), sub.end());
23. }
24. ls = (ls +( (ls - i) * v) % M);
26. }
27. cout<<(ls%M+M)%M<<endl;
28. }
29. return 0;
30. }