题目背景

经过管理员的考虑，我们打算将民间数据单独存放在最后一个 Subtask 中。这些测试点分数均为 0 分，但是没有通过其中的任何测试点将会视为此题不通过。

这一题中出现了评测记录测试点编号错乱的问题，是民间数据命名方式冲突导致的。但是我们保证其相对顺序没有混乱。

民间数据提供者：@tiger2005。

题目描述

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

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

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

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

见附件中的 string2.in

见附件中的 string2.out

提示

【样例 1 解释】

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

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

【数据范围】

对于 $20\%$ 的数据，$n,m\le 15$。

对于 $30\%$ 的数据，$n,m\le 30$。

对于 $70\%$ 的数据，$n,m\le 80$。

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

对于 $100\%$ 的数据，$1\le t\le 5$，$1\le n,m\le 400$。