Cut and Paste
Contest: Codeforces Round 607 (Div. 1)
Difficulty rating: 1700
Tags: implementation, math

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:

1. Perform the Move action once.
2. Perform the Cut action once.
3. Perform the Paste action $$$s_\ell$$$ times.
4. 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 format:
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 format:
For each test case, output a single line containing a single integer denoting the answer for that test case modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
4
5
231
7
2323
6
333
24
133321333

Example output:
25
1438
1101
686531475

Editorial:
Let $$$S^t$$$ be the string $$$S$$$ after the $$$t$$$th round, and let $$$S^0$$$ be the initial $$$S$$$. We also denote by $$$S_{i\ldots }$$$ the suffix of $$$S$$$ from the $$$i$$$th character, $$$S_i$$$, onwards.
A single round turns $$$S^{t-1}$$$ into $$$S^t$$$ by replicating the suffix $$$S_{t+1\ldots }^{t-1}$$$ exactly $$$S_t$$$ times. Hence, we have the recurrence $$$$$$S^t = S^{t-1} + S_{t+1\ldots }^{t-1}\cdot \left(S_t^{t-1} - 1\right),$$$$$$ where $$$+$$$ represents concatenation, and $$$s \cdot n$$$ represents replicating $$$s$$$ $$$n$$$ times. (Note that $$$S_t^{t-1}$$$ is interpreted as an integer.)
In terms of lengths, we have $$$$$$\left|S^t\right| = \left|S^{t-1}\right| + \left|S_{t+1\ldots }^{t-1}\right|\cdot \left(S_t^{t-1} - 1\right).$$$$$$ Since $$$\left|S_{i+1\ldots }\right| = \left|S\right| - i$$$, this is equivalent to $$$$$$\left|S^t\right| = \left|S^{t-1}\right| + \left(\left|S^{t-1}\right| - t\right)\cdot \left(S_t^{t-1} - 1\right).$$$$$$
This cannot be simulated yet as it is since the length of $$$S$$$ could be growing very quickly. But notice that $$$S^{t-1}$$$ is always a prefix of $$$S^t$$$. Therefore, for any two $$$t_1$$$ and $$$t_2$$$, the $$$i$$$th letters of $$$S^{t_1}$$$ and $$$S^{t_2}$$$ are the same (as long as their lengths are at least $$$i$$$). Also, note that we only need to access up to the $$$x$$$th character, $$$S_x$$$. Therefore, we only need to grow $$$S$$$ just enough until it contains at least $$$x$$$ characters. After that, we can stop modifying $$$S$$$ at that point and simply keep track of the length, maintaining it using the recurrence above.
The running time is $$$O(|S| + x)$$$. (But in languages where strings are immutable, you should use a dynamically-resizing list instead of appending strings repeatedly, otherwise, you'll get a running time of $$$O(x^2)$$$.)