Migrated from Lutece 2615 simple string problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

定义

$V(T)=\sum \text{OCC}(s,t)f(t,T)$

其中 $\text{OCC}(s,t)$ 表示为 $t$ 在 $s$ 中出现的次数。如果 $t$ 是 $T$ 的回文子串，则 $f(t,T)=1$，否则 $f(t,T)=0$。

给定一个初始串 $s$ ，维护两种操作：每次在 $s$ 后新加一个字符或者删除一个字符。求对于所有的长度为 $n$ 的字符串 $T$，$V(T)$ 的大小之和。

Input

第一行一个数 $t$ 表示测试组数。 接下来 $t$ 组测试数据，每组测试数据由以下部分组成： 第一行两个数 $n,m$ 和一个字符串 $s$，分别代表 $T$ 的长度，修改次数和字符串 $s$。 接下来 $m$ 行，会以以下形式给出：

• 1 c，代表在 $s$ 之后加入一个新的字符 $c$。
• 2，代表删除 $s$ 的最后一个字符。

Output

输出 $m+1$ 行，每行一个整数。第一个整数代表对于最初的 $s$ 的结果，接下来 $m$ 行，第 $i+1$ 行代表第 $i$ 次操作之后的结果。所有答案对 $10^9+7$ 取模。

Samples

3
1 4 abc
1 a
2
2
1 a
3 4 abc
1 a
2
2
1 a
5 1 sugar
1 r

3
4
3
2
3
6084
8112
6084
4056
6085
11424400
13779584

Constraints

$1\leq t\leq 25$ $1\leq n,m,|s|\leq 5\times 10^5$ $\sum n,\sum m,\sum |s| \leq 2\times 10^6$ 保证 $s$ 中只有小写英文字母。

Resources

2021 UESTC ICPC Training for String and Search Algorithm