3658. [NOI Online 2022 1st PJ]字符串

【题目描述】

Kri 非常喜欢字符串，所以他准备找$t$组字符串研究。

第$i$次研究中， Kri 准备了两个字符串$S$和$R$，其中$S$长度为$n$，且只由 0,1,- 三种字符构成（注：这里的第三种字符是减号）， $R$初始时为空 。

每次研究，Zay 会带着一个美丽的长度为$m$的字符串$T$来找 Kri 玩，Kri 非常羡慕 Zay 拥有如此美丽的字符串，便也想用字符串$S$和$R$变出字符串$T$。

具体地， Kri 将会进行$n$次操作。每次操作中， Kri 会取出$S$的第一个字符(记为$c$)，并将其从$S$中删去。如果$c=-$，则 Kri 要删去$R$的开头字符或结尾字符(数据保证删去后$不为空)。否则，Kri 会将$c$加入到$R$的末尾。

当进行完所有操作后， Kri 会检查$R$是否和$T$相等。如果$R=T$， Kri 就会感到开心；否则， Kri 会感到难受。

请问在每次研究中， Kri 有多少种操作方式使自己最后感到开心？我们定义两种方案不同，当且仅当在某种方案的某次操作中， Kri 删去了$R$的开头字符。而在另一种方案的这次操作中， Kri 删去了$R$的结尾字符。

由于答案可能很大，你只需要输出答案除以 $1,000,000,007$(即$10^9+7$)的余数。

【输入格式】

第一行一个正整数$t$。

接下来有$t$组数据分别表示$t$次字符串的研究，对于每组数据：

第一行有两个正整数$n,m$，分别表示字符串$S,T$的长度。

第二行是字符串$S$。

第三行是字符串$T$。

【输出格式】

共$t$行，第$i$行表示第$i$组研究的答案。

【样例输入】

3
6 2
10-01-
01
7 3
010-1-1
101
6 4
111-00
1100

【样例输出】

2
1
2

测试样例下载

【样例说明】

对于第一组数据，有以下两种方案：

第一个 - 删$R$的开头，第二个 - 删$R$的结尾。

第一个 - 删$R$的结尾，第二个 -删$R$的开头。

【数据规模与约定】

对于20%的数据， $n,m\leq 15$。

对于30%的数据， $n,m\leq 30$。

对于70%的数据， $n,m\leq 80$。

对于另10%的数据， 保证答案不超过1。

对于100%的数据，$1\leq t\leq 5,1\leq n, m\leq 400$。

【来源】

NOI Online 2020 1st 普及组 T3