Cut and Paste (Codeforces 1280A)
Tags: Math, implementation

We start with a string $$$s$$$ consisting only of the digits $$$1$$$, $$$2$$$, or $$$3$$$. The length of $$$s$$$ is denoted by $$$|s|$$$. For each $$$i$$$ from $$$1$$$ to $$$|s|$$$, the $$$i$$$-th character of $$$s$$$ is denoted by $$$s_i$$$. There is one cursor. The cursor's location $$$\ell$$$ is denoted by an integer in $$$\{0, \ldots, |s|\}$$$, with the following meaning:   If $$$\ell = 0$$$, then the cursor is located before the first character of $$$s$$$.  If $$$\ell = |s|$$$, then the cursor is located right after the last character of $$$s$$$.  If $$$0 < \ell < |s|$$$, then the cursor is located between $$$s_\ell$$$ and $$$s_{\ell+1}$$$. We denote by $$$s_\text{left}$$$ the string to the left of the cursor and $$$s_\text{right}$$$ the string to the right of the cursor. We also have a string $$$c$$$, which we call our clipboard, which starts out as empty. There are three types of actions:  The Move action. Move the cursor one step to the right. This increments $$$\ell$$$ once.  The Cut action. Set $$$c \leftarrow s_\text{right}$$$, then set $$$s \leftarrow s_\text{left}$$$.  The Paste action. Append the value of $$$c$$$ to the end of the string $$$s$$$. Note that this doesn't modify $$$c$$$. The cursor initially starts at $$$\ell = 0$$$. Then, we perform the following procedure:  Perform the Move action once.  Perform the Cut action once.  Perform the Paste action $$$s_\ell$$$ times.  If $$$\ell = x$$$, stop. Otherwise, return to step 1. 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 $$$10^9 + 7$$$. It is guaranteed that $$$\ell \le |s|$$$ at any time.

Input: The first line of input contains a single integer $$$t$$$ ($$$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$$$ ($$$1 \le x \le 10^6$$$). The second line of each test case consists of the initial string $$$s$$$ ($$$1 \le |s| \le 500$$$). It is guaranteed, that $$$s$$$ consists of the characters "1", "2", "3".It is guaranteed that the sum of $$$x$$$ in a single file is at most $$$10^6$$$. It is guaranteed that in each test case before the procedure will stop it will be true that $$$\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 $$$10^9 + 7$$$. 

Note: Let's illustrate what happens with the first test case. Initially, we have $$$s = $$$ 231. Initially, $$$\ell = 0$$$ and $$$c = \varepsilon$$$ (the empty string). The following things happen if we follow the procedure above:  Step 1, Move once: we get $$$\ell = 1$$$.  Step 2, Cut once: we get $$$s = $$$ 2 and $$$c = $$$ 31.  Step 3, Paste $$$s_\ell = $$$ 2 times: we get $$$s = $$$ 23131.  Step 4: $$$\ell = 1 \not= x = 5$$$, so we return to step 1.   Step 1, Move once: we get $$$\ell = 2$$$.  Step 2, Cut once: we get $$$s = $$$ 23 and $$$c = $$$ 131.  Step 3, Paste $$$s_\ell = $$$ 3 times: we get $$$s = $$$ 23131131131.  Step 4: $$$\ell = 2 \not= x = 5$$$, so we return to step 1.   Step 1, Move once: we get $$$\ell = 3$$$.  Step 2, Cut once: we get $$$s = $$$ 231 and $$$c = $$$ 31131131.  Step 3, Paste $$$s_\ell = $$$ 1 time: we get $$$s = $$$ 23131131131.  Step 4: $$$\ell = 3 \not= x = 5$$$, so we return to step 1.   Step 1, Move once: we get $$$\ell = 4$$$.  Step 2, Cut once: we get $$$s = $$$ 2313 and $$$c = $$$ 1131131.  Step 3, Paste $$$s_\ell = $$$ 3 times: we get $$$s = $$$ 2313113113111311311131131.  Step 4: $$$\ell = 4 \not= x = 5$$$, so we return to step 1.   Step 1, Move once: we get $$$\ell = 5$$$.  Step 2, Cut once: we get $$$s = $$$ 23131 and $$$c = $$$ 13113111311311131131.  Step 3, Paste $$$s_\ell = $$$ 1 times: we get $$$s = $$$ 2313113113111311311131131.  Step 4: $$$\ell = 5 = x$$$, so we stop. At the end of the procedure, $$$s$$$ has length $$$25$$$. 

Sample Inputs:
4
5
231
7
2323
6
333
24
133321333

Sample Outputs:
25
1438
1101
686531475

Solution (Python):
def solve(x, s):
    (len_, s) = (len(s), list(s))
    for e in range(1, x + 1):
        r = int(s[e - 1])
        if len(s) < x and r > 1:
            s += s[e:] * (r - 1)
        len_ = (e + (len_ - e) * r) % 1000000007
    return len_
for T in range(int(input())):
    print(solve(int(input()), input()))

Solution (Python):
for _ in range(int(input())):
    x = int(input())
    s = input()
    l = 0
    while len(s) < x:
        s += s[l + 1:] * (int(s[l]) - 1)
        l += 1
    ls = len(s)
    for k in range(l, x):
        ls += (ls - k - 1) * (int(s[k]) - 1)
        ls %= 10 ** 9 + 7
    print(ls)

Solution (Python):
import sys
mod = 10 ** 9 + 7
for _ in range(int(input())):
    x = int(input())
    s = list(map(int, input()))
    ans = len(s)
    for i in range(1, x + 1):
        ans = (i + (ans - i) * s[i - 1]) % mod
        r = len(s)
        for _ in range(s[i - 1] - 1):
            if len(s) < x:
                s += s[i:r]
            else:
                break
    print(ans)