Cut and Paste (Codeforces 1281C)
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):
MOD = 10 ** 9 + 7

def main():
    x = int(input())
    s = input()
    ln = len(s)
    key = 0
    for l in range(x):
        num = int(s[l]) - 1
        if num == 0:
            continue
        if ln < x and (not key):
            s += s[l + 1:] * num
        r = (ln - l - 1) * num
        ln += r
        if ln >= MOD:
            key = 1
        ln %= MOD
    print(ln % MOD)
t = int(input())
for _ in range(t):
    main()

Solution (Python):
for i in range(int(input())):
    x = int(input())
    s = input()
    ans = len(s)
    a = x
    for j in range(1, x + 1):
        if s[j - 1] == '1':
            pass
        elif s[j - 1] == '2':
            ans += ans - j
            ans %= 10 ** 9 + 7
            s = s + s[j:]
        elif s[j - 1] == '3':
            ans += 2 * (ans - j)
            ans %= 10 ** 9 + 7
            s = s + 2 * s[j:]
        if len(s) > x:
            a = j
            break
    for k in range(a + 1, x + 1):
        if s[k - 1] == '1':
            pass
        elif s[k - 1] == '2':
            ans += ans - k
            ans %= 10 ** 9 + 7
        elif s[k - 1] == '3':
            ans += 2 * (ans - k)
            ans %= 10 ** 9 + 7
    ans %= 10 ** 9 + 7
    print(ans)

Solution (Python):
from collections import deque

def solve():
    n = int(input())
    t = [int(a) for a in input()]
    prawo = len(t) - 1
    kolejkaMnozen = deque([])
    idx = 0
    lMnozenia = 1
    for i in range(n):
        while idx >= len(t):
            if len(kolejkaMnozen) == 0:
                exit(666)
            if kolejkaMnozen[0] != 1:
                t.extend((kolejkaMnozen[0] - 1) * t[lMnozenia:])
            lMnozenia += 1
            kolejkaMnozen.popleft()
        mnoznik = t[idx]
        prawo = prawo * mnoznik
        prawo -= 1
        prawo %= 1000000007
        kolejkaMnozen.append(t[idx])
        idx += 1
    return (n + prawo + 1) % 1000000007
n = int(input())
for i in range(n):
    print(solve())