Background

Due to issues with the testdata, in this problem you do not need to consider non-trivial cases where two different groups of numbers have the same product (cases are considered trivial if they both contain $0$, or differ only by some number of $1$'s, or only differ in order), for example $t\times2\times3=t\times6$. Alternatively, you should treat $\times 2,3,4,5,6,7,8,9$ in the statement as $\times 2,3,5,7,11,13,17,19$, respectively.

Problem Description

A program consists of a sequence of instructions, and each instruction has one of the following forms:

• $\times d$, where $d$ is a single digit in the range $[0,9]$.
• $+s$, where $s$ is a string representing a variable name. All variable names appearing in a program are distinct.

The result of executing a program is defined as the expression obtained by applying each instruction in order to the expression $0$. For example, executing the program $[\times 3,+x,+y,\times 2,+z]$ produces the expression $(0\times 3+x+y)\times 2+z=2 \times x+2\times y+z$. Different programs may produce the same expression after execution; for example, executing $[+w,\times 0,+y,+x,\times 2,+z,\times 1]$ also produces the expression $2\times x+2\times y+z$.

Bessie and Elsie each have a program with $N$ instructions ($1\le N\le 2000$). They will interleave the instructions of these programs to create a new program with $2N$ instructions. Note that there are $\frac{(2N)!}{N!\times N!}$ ways to do this, but not all such programs produce different expressions after execution.

Compute the number of distinct expressions that can result from executing an interleaving of Bessie's and Elsie's programs, modulo $10^9+7$.

Each test file contains $T$ subtestcases ($1\le T\le 10$) that should be solved independently. The input guarantees that the sum of $N$ over all subtestcases does not exceed $2000$.

Input Format

The first line of input contains $T$, the number of subtestcases.

For each subtestcase, the first line contains $N$.

The second line of each subtestcase contains Bessie's program, represented as a string of length $N$. Each character is either a single digit $d\in [0,9]$, representing an instruction of type 1, or the character $+$, representing an instruction of type 2.

The third line of each subtestcase contains Elsie's program, in the same format as Bessie's program.

Within a subtestcase, all variable names in all instructions are distinct. Note that their actual names are not given here, because they do not affect the answer.

Output Format

Output the number of distinct expressions that can result from executing an interleaving of Bessie's and Elsie's programs, modulo $10^9+7$.

4
1
0
1
3
12+
+02
3
0++
++9
4
5+++
+6+1

1
3
9
9

Hint

【Sample Explanation】

For the first subtestcase, the two interleavings that can be created are $[\times 1, \times 0]$ and $[\times 0,\times 1]$. After execution, both produce the expression $0$.

For the second subtestcase, executing the interleavings of $[\times 1,\times 2, +x]$ and $[+y, \times 0,\times 2]$ can produce one of the expressions $0$, $x$, and $2\times x$.

【Test Point Properties】

• Test point 2 satisfies $N\le 6$.
• In test points 3-5, the sum of all $N$ does not exceed $100$.
• In test points 6-8, the sum of all $N$ does not exceed $500$.
• Test points 9-16 have no additional constraints.

Translated by ChatGPT 5