Description
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 的开头字符或结尾字符（数据保证删去后 R 不为空）。否则，Kri 会将 c 加入到 R 的末尾。
当进行完所有操作后，Kri 会检查 R 是否和 T 相等。如果 R = T，Kri 就会感到开心；否则，Kri 会感到难受。
请问在每次研究中，Kri 有多少种操作方式使自己最后感到开心？我们定义两种方案不同，当且仅当在某种方案的某次操作中， Kri 删去了 R 的开头字符。而在另一种方案的这次操作中， Kri 删去了 R 的结尾字符。
由于答案可能很大，你只需要输出答案除以 1,000,000,007（即 109+7）的余数。
Input
第一行一个正整数 t。
接下来有 t 组数据分别表示 t 次字符串的研究，对于每组数据：
第一行有两个正整数 n,m，分别表示字符串 S,T 的长度。
第二行是字符串 S。
第三行是字符串 T。
Output
共 t 行，第 i 行表示第 i 组研究的答案。
3
6 2
10-01-
01
7 3
010-1-1
101
6 4
111-00
1100
HINT
【样例 1 解释】
对于第一组数据，有以下两种方案：
-
第一个 - 删 R 的开头，第二个 - 删 R 的结尾。
-
第一个 - 删 R 的结尾，第二个 - 删 R 的开头。
样例二：
string.zip
【数据范围】
对于 20% 的数据，n,m≤15。
对于 30% 的数据，n,m≤30。
对于 70% 的数据，n,m≤80。
对于另 10% 的数据，保证答案不超过 1。
对于 100% 的数据，1≤t≤5，1≤n,m≤400。