#5185. 字符串

字符串

题目描述

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

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

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

具体地, Kri 将会进行 nn 次操作。每次操作中, Kri 会取出 SS 的第一个字符(记为 cc),并将其从 SS 中删去。如果 c=-c=\text{-} ,则 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 组研究的答案。

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

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

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

输入输出数据 2

见附件中的 string2.instring2.out

数据范围

对于 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\% 的数据,1t5, 1n,m4001 \le t \le 5,~1 \le n,m \le 400