Interleaved Linear Programs

You are given two programs, each consisting of N (1 ≤ N ≤ 2000) instructions. Each instruction is one of the following two types:

• * d where d is a single digit (0 ≤ d ≤ 9). This represents a multiplication instruction.
• +s where s is a string representing a variable name. In each program the variable names are all distinct.

A program is executed on the initial expression 0 by applying each instruction in order. A multiplication instruction * d transforms the current expression E into d·E, while an addition instruction +s transforms E into E+s. Thus, if we execute the program

[ * 3, +x, +y, * 2, +z ]

the execution is as follows:

1. Start with 0.
2. * 3: 0 becomes 0.
3. +x: 0 becomes x.
4. +y: x becomes x+y.
5. * 2: x+y becomes 2x+2y.
6. +z: 2x+2y becomes 2x+2y+z.

The final result of executing a program is the expression obtained after applying all instructions. Note that if there are multiplication instructions after an addition, the contribution of that addition gets multiplied accordingly. In other words, if the merged sequence of instructions is f₁, f₂, …, f_2N and if we denote an addition instruction +s by the linear function f(x)=x+s (with s being treated as an independent variable) and a multiplication instruction * d by f(x)=d·x, then the composition of the functions applied on 0 gives a linear expression only in the added variables.

Bessie and Elsie each have a program of N instructions. They produce a new program of 2N instructions by interleaving the two programs (i.e. merging them while preserving the relative order of the instructions in each program). There are C(2N, N) possible interleavings. However, different interleavings may result in the same final expression. For example, even though

[ +w, * 0, +y, +x, * 2, +z, * 1 ]

and

[ * 3, +x, +y, * 2, +z ]

are different programs (note: these examples come from two different original programs), the final expression might coincide after cancellation of the effect of the multiplications (when viewed as a linear transformation on 0). More precisely, each addition +s in the merged program contributes with a coefficient equal to the product of all multiplier digits in the instructions after it.

Your task is to compute the number of distinct final expressions obtainable by interleaving the two programs, modulo 10⁹+7.

Observation and Hint

Since the two original programs preserve the order of their instructions, each program has its own fixed pattern of additions and multiplications. If we denote by a the number of addition instructions and m the number of multiplication instructions in a program then the final expression is of the form

x₁·P₁ + x₂·P₂ + ...

where each coefficient is the product of a fixed suffix (from that program) and a choice of a suffix of multiplier instructions from the other program. It can be shown that the distinct outcomes are counted by

C(m_other + (# of additions), (# of additions))

for each program, and the total number of distinct outcomes is the product of the two counts modulo 10⁹+7.

More formally, let Bessie's program have a_B addition instructions and m_B multiplication instructions, and Elsie's program have a_E addition instructions and m_E multiplication instructions. Then the answer is:

Ans = C(m_E + a_B, a_B) × C(m_B + a_E, a_E) (mod 10⁹+7)

You need to compute this value.

inputFormat

The first line contains a single integer T (1 ≤ T ≤ 10), the number of test cases. Then T test cases follow. Each test case begins with an integer N (1 ≤ N ≤ 2000), the number of instructions in each program.

The next line contains N space‐separated instructions representing Bessie’s program.

The following line contains N space‐separated instructions representing Elsie’s program.

Each instruction is either of the form *d (where d is a digit from 0 to 9) or +s (where s is a variable name consisting of lowercase letters). In each program, all variable names are distinct.

outputFormat

For each test case, output a single line containing one integer — the number of distinct final expressions modulo 10⁹+7.

sample

3
1
+x
*d
2
+x +y
*3 +z
3
*3 +x +y
+w *0 +v

1
3
6