Background

After consideration by the administrators, we plan to store the unofficial testdata separately in the last Subtask. These test points all have a score of 0, but failing to pass any of them will be considered as not passing this problem.

In this problem, there was an issue where the test point numbers in the judging records were in a mess. This was caused by a naming conflict in the unofficial testdata. However, we guarantee that their relative order is not mixed up.

Unofficial testdata provider: @tiger2005.

Problem Description

Kri really likes strings, so he prepares to study $t$ groups of strings.

In the $i$-th study, Kri prepares two strings $S$ and $R$. Here, $S$ has length $n$ and consists only of the three characters 0, 1, and - (note: the third character is a minus sign). Initially, $R$ is empty.

In each study, Zay comes to play with Kri, bringing a beautiful string $T$ of length $m$. Kri is very envious that Zay has such a beautiful string, so he also wants to use strings $S$ and $R$ to produce string $T$.

Specifically, Kri will perform $n$ operations. In each operation, Kri takes the first character of $S$ (denoted as $c$) and deletes it from $S$. If $c = \texttt{-}$, then Kri must delete the first character or the last character of $R$ (the testdata guarantees that after deletion, $R$ is not empty). Otherwise, Kri appends $c$ to the end of $R$.

After all operations are finished, Kri checks whether $R$ is equal to $T$. If $R = T$, Kri will feel happy; otherwise, Kri will feel sad.

For each study, how many different ways of operating will make Kri happy in the end? We define two plans as different if and only if, in some operation of some plan, Kri deletes the first character of $R$, while in the corresponding operation of the other plan, Kri deletes the last character of $R$.

Since the answer may be very large, you only need to output the remainder of the answer modulo $1,000,000,007$ (i.e. $10^9+7$).

Input Format

The first line contains a positive integer $t$.

Then there are $t$ test cases, representing $t$ studies of strings. For each test case:

The first line contains two positive integers $n, m$, representing the lengths of strings $S$ and $T$.

The second line is the string $S$.

The third line is the string $T$.

Output Format

Output $t$ lines in total. The $i$-th line denotes the answer for the $i$-th test case.

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

2
1
2

见附件中的 string2.in

见附件中的 string2.out

Hint

[Sample 1 Explanation]

For the first test case, there are two plans as follows:

• The first - deletes the first character of $R$, and the second - deletes the first character of $R$.
• The first - deletes the last character of $R$, and the second - deletes the first character of $R$.

[Constraints]

For $20\%$ of the testdata, $n, m \le 15$.

For $30\%$ of the testdata, $n, m \le 30$.

For $70\%$ of the testdata, $n, m \le 80$.

For the other $10\%$ of the testdata, it is guaranteed that the answer does not exceed $1$.

For $100\%$ of the testdata, $1 \le t \le 5$, $1 \le n, m \le 400$.

Translated by ChatGPT 5