CF1280A.Cut and Paste

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 \lt \ell \lt |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.

我们从一个仅由数字 $1$、$2$ 或 $3$ 组成的字符串 $s$ 出发。$s$ 的长度记为 $|s|$。对每个从 $1$ 到 $|s|$ 的整数 $i$，$s$ 的第 $i$ 个字符记为 $s_i$。

有一个光标。光标的位置 $\ell$ 是一个取值于 $\{0, \ldots, |s|\}$ 的整数，其含义如下：

• 若 $\ell = 0$，则光标位于 $s$ 的第一个字符之前；
• 若 $\ell = |s|$，则光标位于 $s$ 的最后一个字符之后；
• 若 $0 \lt \ell \lt |s|$，则光标位于 $s_\ell$ 与 $s_{\ell+1}$ 之间。

记 $s_\text{left}$ 为光标左侧的子串，$s_\text{right}$ 为光标右侧的子串。

此外，我们还有一个字符串 $c$，称为剪贴板（clipboard），初始为空。共有三种操作：

• 移动（Move）操作：将光标向右移动一步，即 $\ell$ 增加 $1$；
• 剪切（Cut）操作：令 $c \leftarrow s_\text{right}$，然后令 $s \leftarrow s_\text{left}$；
• 粘贴（Paste）操作：将 $c$ 的当前值追加到字符串 $s$ 的末尾（注意：该操作不改变 $c$）。

光标初始位置为 $\ell = 0$。随后，我们执行以下过程：

1. 执行一次 Move 操作；
2. 执行一次 Cut 操作；
3. 执行 $s_\ell$ 次 Paste 操作（注意：此处 $s_\ell$ 表示当前字符串 $s$ 中下标为 $\ell$ 的字符所代表的数字，即若 $s_\ell = '2'$，则执行 2 次 Paste）；
4. 若 $\ell = x$，则停止；否则返回步骤 1。

给定初始字符串 $s$ 和整数 $x$，求该过程停止时 $s$ 的长度。由于该值可能极大，请只输出它对 $10^9 + 7$ 取模的结果。

保证在任意时刻均有 $\ell \le |s|$。

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.

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。接下来的若干行包含各测试用例的描述。

每个测试用例的第一行包含一个整数 $x$（$1 \le x \le 10^6$）。每个测试用例的第二行包含初始字符串 $s$（$1 \le |s| \le 500$）。保证字符串 $s$ 仅由字符 "1"、"2"、"3" 组成。

保证单个输入文件中所有测试用例的 $x$ 值之和不超过 $10^6$。保证在每个测试用例中，程序停止前任意时刻均有 $\ell \le |s|$ 成立。

For each test case, output a single line containing a single integer denoting the answer for that test case modulo $10^9 + 7$.

对于每个测试用例，输出一行，包含一个整数，表示该测试用例的答案对 $10^9 + 7$ 取模的结果。

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

我们以第一个测试用例为例说明整个过程。初始时，$s = $ 231，$\ell = 0$，且 $c = \varepsilon$（空字符串）。若按上述步骤执行，将发生以下操作：

• 第 1 步，移动一次：得到 $\ell = 1$。

• 第 2 步，剪切一次：得到 $s = $ 2，$c = $ 31。

• 第 3 步，粘贴 $s_\ell = $ 2 次：得到 $s = $ 23131。

• 第 4 步：$\ell = 1 \not= x = 5$，因此返回第 1 步。

• 第 1 步，移动一次：得到 $\ell = 2$。

• 第 2 步，剪切一次：得到 $s = $ 23，$c = $ 131。

• 第 3 步，粘贴 $s_\ell = $ 3 次：得到 $s = $ 23131131131。

• 第 4 步：$\ell = 2 \not= x = 5$，因此返回第 1 步。

• 第 1 步，移动一次：得到 $\ell = 3$。

• 第 2 步，剪切一次：得到 $s = $ 231，$c = $ 31131131。

• 第 3 步，粘贴 $s_\ell = $ 1 次：得到 $s = $ 23131131131。

• 第 4 步：$\ell = 3 \not= x = 5$，因此返回第 1 步。

• 第 1 步，移动一次：得到 $\ell = 4$。

• 第 2 步，剪切一次：得到 $s = $ 2313，$c = $ 1131131。

• 第 3 步，粘贴 $s_\ell = $ 3 次：得到 $s = $ 2313113113111311311131131。

• 第 4 步：$\ell = 4 \not= x = 5$，因此返回第 1 步。

• 第 1 步，移动一次：得到 $\ell = 5$。

• 第 2 步，剪切一次：得到 $s = $ 23131，$c = $ 13113111311311131131。

• 第 3 步，粘贴 $s_\ell = $ 1 次：得到 $s = $ 2313113113111311311131131。

• 第 4 步：$\ell = 5 = x$，因此停止。

该过程结束时，$s$ 的长度为 $25$。