Deque Operations and Substring Reconstruction

Kri loves strings and is studying them for t test cases. In the i-th test case, Kri has a string S of length n which consists only of the characters 0, 1, and - (the minus sign). Kri also maintains an initially empty string R.

Zay then brings a beautiful string T of length m. Kri wants to use S to transform R such that at the end of a process they obtain T.

The process consists of n operations. In each operation, Kri removes the first character c from S (thereby shortening S). If c = -, then Kri must delete either the first character or the last character from R. It is guaranteed that after such a deletion R will not become empty. Otherwise (that is, if c is 0 or 1), Kri appends c to the end of R.

After all operations, if R exactly equals T, then Kri is happy; otherwise, Kri is sad.

Your task is to compute the number of distinct sequences of choices (i.e. choices of deleting from the beginning or the end in the deletion operations) that make Kri happy. Two sequences are considered different if there is at least one operation where one sequence deletes the first character of R and the other deletes the last character. Since the answer can be very large, output it modulo \(10^9+7\).

---

Note on the Process

Let us denote by \(A\) the sequence of characters in S other than - (i.e. the digits appended in order). Since every deletion operation removes one character from either end of the current string, the final string is always a contiguous substring of \(A\). Furthermore, if \(p=|A|\) and there are \(d\) deletion operations in S, then the final string has length \(p-d\). Therefore, a necessary condition for obtaining \(T\) is:

[ p - d = m. ]

If we let \(L\) be the number of deletions performed from the front (and thus \(d-L\) from the back), then the final string is \(A[L+1\ldots p-(d-L)]\) (using 1-indexing), i.e. the contiguous segment of \(A\) starting at index \(L\) (0-indexed) of length \(m\). If this segment equals \(T\), then there are \(\binom{d}{L}\) ways to order the deletion choices to achieve that.

Your task is to sum \(\binom{d}{L}\) over all \(L\) (from \(0\) to \(d\)) for which the corresponding contiguous segment of \(A\) equals \(T\), and output the result modulo \(10^9+7\>.

inputFormat

The first line contains an integer t (\(1 \le t\le 10^4\)), representing the number of test cases. For each test case, there are two lines:

• The first line contains the string S (\(1 \le |S| \le 10^5\)), consisting of characters '0', '1', and '-'.
• The second line contains the target string T (\(1 \le |T| \le |S|\)).

It is guaranteed that for each deletion (i.e. each occurrence of '-' in S), the process is such that upon removal of a character from R, R does not become empty.

outputFormat

For each test case, output a single line containing the number of ways Kri can perform the operations so that the final string R equals T, modulo \(10^9+7\).

sample

4
10-
0
101--
1
11-0-
1
10-1
11

1
2
3
0

</p>