【题目描述】

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中 删去。如果 - ，则 Kri 要删去R 的开头字符或结尾字符（数据保证删去后 R不为空）。否则， Kri 会将 c加入到R 的末尾。

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

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

 由于答案可能很大，你只需要输出答案除以1,000,000,007 （即109+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`-1

【样例解释】

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

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

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

【数据范围】

对于20%的数据，n,m<=15 。 

对于30 的数据， n，m<=30。 

对于 70%的数据，n,m<=80 。 

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

对于100% 的数据，1<=t<=5,  1<=n,m<=400 。

(adsbygoogle = window.adsbygoogle || []).push({});