CF1280A Cut and Paste

我们有一个只包含数字 $1$、$2$ 或 $3$ 的字符串 $s$。字符串的长度记为 $|s|$。对于每个 $i$，$1 \leq i \leq |s|$，$s_i$ 表示 $s$ 的第 $i$ 个字符。 有一个光标，光标的位置 $\ell$ 用一个整数表示，取值范围为 $\{0, \ldots, |s|\}$，含义如下： - 如果 $\ell = 0$，则光标位于 $s$ 的第一个字符之前。 - 如果 $\ell = |s|$，则光标位于 $s$ 的最后一个字符之后。 - 如果 $0 < \ell < |s|$，则光标位于 $s_\ell$ 和 $s_{\ell+1}$ 之间。 我们用 $s_\text{left}$ 表示光标左侧的字符串，$s_\text{right}$ 表示光标右侧的字符串。 我们还有一个字符串 $c$，称为剪贴板，初始为空。可以进行以下三种操作： - 移动操作（Move）：将光标向右移动一格，即 $\ell$ 增加 $1$。 - 剪切操作（Cut）：令 $c \leftarrow s_\text{right}$，然后令 $s \leftarrow s_\text{left}$。 - 粘贴操作（Paste）：将 $c$ 的内容追加到 $s$ 的末尾。注意，这不会改变 $c$ 的内容。 光标初始时位于 $\ell = 0$。然后，按照如下过程操作： 1. 执行一次移动操作。 2. 执行一次剪切操作。 3. 执行 $s_\ell$ 次粘贴操作。 4. 如果 $\ell = x$，则停止。否则，返回第 1 步。 给定初始字符串 $s$ 和整数 $x$，问当过程结束时，$s$ 的长度是多少？由于答案可能很大，只需输出其对 $10^9 + 7$ 取模的结果。 保证在任何时刻都有 $\ell \leq |s|$。

输入的第一行为一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。接下来每组测试用例包含如下内容： 每个测试用例的第一行为一个整数 $x$（$1 \leq x \leq 10^6$）。第二行为初始字符串 $s$（$1 \leq |s| \leq 500$）。保证 $s$ 仅由字符 "1"、"2"、"3" 组成。 保证单个文件中所有 $x$ 的和不超过 $10^6$。保证在每个测试用例中，过程结束前始终有 $\ell \leq |s|$。

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

以下用第一个测试用例举例说明过程。初始时，$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$。 由 ChatGPT 4.1 翻译