C.Cut and Paste

题意：我们由一个以1, 2, 3组成的字符串s开始，s的长度记为|s|，第i个字符记为si
这里有一个光标，光标的位置l在{0, ..., |s|}范围中
如果l = 0，光标的位置在第一个字符前面
如果l = |s|，光标的位置在最后一个字符的后面
如果0 < l < |s|，那么光标的位置在字符sl和sl+1之间

我们有一个字符串c，叫做裁剪板，一开始是空的

这里有3种操作：
1.移动操作:移动光标一步到右边，l增加一次
2.裁剪操作:让Sright右边的字符到c中，让Sleft左边的字符到s中(光标位置坐标和光标位置右边)
3.粘贴操作:追加字符串c到字符串s的后面

一开始l的位置为0，我们进行如下的操作：
1.执行移动操作一次
2.执行裁剪操作一次
3.执行粘贴操作Sl次(Sl表示光标位置坐标的数字)
4.如果l == x，停止，否则回到步骤一

输入：
给出t组测试数据，每组测试数据为x(1 <= x <= 10^6)，第二行是字符串s

输出：
对于每一组测试，当这些步骤执行完毕后，对s的长度模 10 ^ 9 + 7，输出答案

分析：让我们称(s^t)为字符串s经过t轮后的字符串，称(s^0)为初始的字符串s，称(s_idots)为字符串s的后面i个字符，
那么，我们可以得到(s^t)由(s^{t-1})得到的公式:

[s^t = s^{t-1} + s^{t-1}_{t+1}dots imes(s^{t-1}_{t} - 1) ]

其中，+表示连接字符串的意思，这个公式表示原先的字符串再追加上当前光标右边的所有字符乘以光标所在位置的数字-1的次数
那么可以得到如下公式
$$|s^t| = |s^{t-1}| + |s^{{t-1}_{t+1}dots| imes(s}{t-1}_t - 1)$$
因为(|s_{i+1}dots| = |s| - i)，
因此如上的公式可以替换成如下的公式：
$$|s^t| = |s^{t-1}| + (|s^{t-1}| - t) imes(s^{t-1}_t - 1)$$
我们最多访问到第x个字符，我们可以发现对于任意两个t1和t2，对于(s^{t1})和(s^{t2})，如果它们的前i个字符是一样的，意味着它们至少含有i个字符，
那么我们就不需要l == x才停止，我们可以判断s字符串是否有x个字符串才停止，之后，再利用公式进行计算。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
using LL = long long;

const int mod = 1e9 + 7;

const int N = 505;
char s[N];

LL solve()
{
	//停止的字符编号
	int x;
	scanf("%d%s", &x, &s);
	LL len = strlen(s);
	vector<char> obj(s, s + len);
	for (int i = 1; i <= x; ++i)
	{
		//需要增加的长度
		int v = obj[i - 1] - '1';
		//只需要至少x个字符就可以了
		if (obj.size() < x)
		{
			vector<char> sub(obj.begin() + i, obj.end());
			for (int j = 0; j < v; ++j)
				obj.insert(obj.end(), sub.begin(), sub.end());
		}
		len = (len + (len - i) * v) % mod;
	}
	return len;
}

int main()
{
	int t;
	scanf("%d", &t);

	while (t--)
	{
		printf("%lld
", (solve() % mod + mod) % mod);
	}



	return 0;
}