#6165. [NOI Online 2022 普及组] 字符串 暂未评定

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

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

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

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

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

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

由于答案可能很大，你只需要输出答案除以 （即 ）的余数。

第一行一个正整数 。

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

第一行有两个正整数 ，分别表示字符串 的长度。

第二行是字符串 。

第三行是字符串 。

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

样例输入 1

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

样例输出 1

2
1
2

样例解释 1

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

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

样例输入 2

见附件中的 string2.in

样例输出 2

见附件中的 string2.out

附件下载

string.zip

对于 的数据，。

对于 的数据，。

对于 的数据，。

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

对于 的数据，，。