Pair Programming

A program consists of a sequence of instructions. Each instruction is one of the following forms:

1. $\times d$, where $d$ is a digit in the range $[0,9]$
2. $+s$, where $s$ is a string denoting the name of a variable. Within a program, all variable names must be distinct.

The result of executing a program is the expression that results after applying each instruction in order, starting with $0$. For example, the result of executing the program $[\times 3,+x,+y,\times 2,+z]$ is the expression $(0\times 3+x+y)\times 2+z=2\times x+2\times y+z$. Different programs may produce the same expression when executed. For example, executing $[+w,\times 0,+y,+x,\times 2,+z,\times 1]$ also results in the expression $2\times x+2\times y+z$.

Bessie and Elsie each have a program of $N$ ($1\le N\le 2000$) instructions. They interleave these programs to produce a new program of length $2N$. There are $\frac{(2N)!}{N!\times N!}$ ways to do this, but not all of them produce distinct expressions when executed.

Count the number of distinct expressions that may be produced by executing Bessie and Elsie's interleaved program, modulo $10^9+7$.

The first line of the input contains $T$, the number of test cases. Each test case is solved independently, with $1\le T\le 10$, and the sum of $N$ over all test cases does not exceed $2000$.

The first line of each test case contains $N$.

The second line of each test case contains Bessie's program, a string of length $N$. Each character is either a 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 test case contains Elsie's program in the same format as Bessie's.

Within a test case, the variable names among all instructions are distinct. Their actual names are not provided, since they do not affect the answer.

Print the number of distinct expressions that may be produced by executing Bessie and Elsie's interleaved programs, modulo $10^9+7$.

For the first test case, the two possible interleaved programs are $[\times 1, \times 0]$ and $[\times 0,\times 1]$. Both produce the expression $0$ when executed.

For the second test case, executing an interleaving of $[\times 1,\times 2, +x]$ and $[+y, \times 0,\times 2]$ could produce one of the expressions $0$, $x$, or $2\times x$.