← 返回题目列表

Codeforces · 1280/A

A. 剪切和粘贴

中文机器翻译题面 查看原题

我们从一个字符串 $$$s$$$ 开始,仅包含数字 $$$1$$$、$$$2$$$ 或 $$$3$$$。 $$$s$$$ 的长度用$$$|s|$$$ 表示。对于从 $$$1$$$ 到 $$$|s|$$$ 的每个 $$$i$$$,$$$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$$$,我们称之为剪贴板,它一开始是空的。共有三种类型的操作:

- 移动操作。将光标向右移动一步。这会增加 $$$\ell$$$ 一次。
- 剪切操作。设置$$$c \leftarrow s_\text{right}$$$,然后设置$$$s \leftarrow s_\text{left}$$$。
- 粘贴操作。将 $$$c$$$ 的值附加到字符串 $$$s$$$ 的末尾。请注意,这不会修改 $$$c$$$。

光标最初从 $$$\ell = 0$$$ 开始。然后,我们执行以下过程:

1. 执行一次移动操作。
2. 执行一次剪切操作。
3. 执行粘贴操作 $$$s_\ell$$$ 次。
4. 如果 $$$\ell = x$$$,则停止。否则,返回步骤 1。

给定初始字符串 $$$s$$$ 和整数 $$$x$$$。当程序停止时,$$$s$$$ 的长度是多少?由于该值可能非常大,因此只需对 $$$10^9 + 7$$$ 求模即可。

保证任何时候$$$\ell \le |s|$$$。

输入

输入的第一行包含一个整数 $$$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|$$$ 在任何时候都为真。

输出

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

示例

输入 #1

4
5
231
7
2323
6
333
24
133321333

输出 #1

25
1438
1101
686531475

注意

让我们说明第一个测试用例会发生什么。最初,我们有 $$$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$$$。