Cut and Paste

题意翻译

给一个串$s$(下标从1到$n)$,和一个变量$it$,初始为$0$.要你执行$x$次操作,求最后的串长度对$10^9+7$取模的结果. 操作如下: 1. 将$it+1$ 2. 将剪贴板的内容替换为$[it,n]$($n$是当前的串的长度),并在原串中删除$[it,n]$ 3. 在串的末尾把剪贴板内容粘贴$s_{it}$次 $x\le 10^6$,原串长度$\le 500$

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

4
5
231
7
2323
6
333
24
133321333

输出样例 #1

25
1438
1101
686531475

说明

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