#A97. [NOI Online 2022 入门组] 字符串

[NOI Online 2022 入门组] 字符串

题目描述

Kri 非常喜欢字符串,所以他准备找 tt 组字符串研究。

ii 次研究中,Kri 准备了两个字符串 SSRR ,其中 SS 长度为 nn,且只由 0, 1, - 三种字符构成(注:这里的第三种字符是减号),RR 初始时为空。

每次研究,Zay 会带着一个美丽的长度为 mm 的字符串 TT 来找 Kri 玩,Kri 非常羡慕 Zay 拥有如此美丽的字符串,便也想用字符串 SSRR 变出字符串 TT

具体地,Kri 将会进行 nn 次操作。每次操作中,Kri 会取出 SS 的第一个字符(记为 cc),并将其从 SS 中删去。如果 c=-c = \texttt{-},则 Kri 要删去 RR 的开头字符或结尾字符(数据保证删去后 RR 不为空)。否则,Kri 会将 cc 加入到 RR 的末尾。

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

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

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

输入格式

第一行一个正整数 tt

接下来有 tt 组数据分别表示 tt 次字符串的研究,对于每组数据:

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

第二行是字符串 SS

第三行是字符串 TT

输出格式

tt 行,第 ii 行表示第 ii 组研究的答案。

样例 #1

样例输入 #1

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

样例输出 #1

2
1
2

样例 #2

样例输入 #2

见文件中的 string2.in

样例输出 #2

见文件中的 string2.out

提示

【样例 1 解释】

对于第一组数据,有以下两种方案:

  • 第一个 -RR 的开头,第二个 -RR 的开头。
  • 第一个 -RR 的结尾,第二个 -RR 的开头。

【数据范围】

对于 20%20\% 的数据,n,m15n,m\le 15

对于 30%30\% 的数据,n,m30n,m\le 30

对于 70%70\% 的数据,n,m80n,m\le 80

对于另 10%10\% 的数据,保证答案不超过 11

对于 100%100\% 的数据,1t51\le t\le 51n,m4001\le n,m\le 400