A program consists of a sequence of instructions, each of which is of one of the following forms:

1. ×d×d, where dd is a digit in the range [0,9][0,9]
2. **+**s+s, where ss 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 defined to be the expression that results after applying each instruction in order, starting with 00. For example, the result of executing the program [×3,+x,+y,×2**,+z][×3,+x,+y,×2,+z] is the expression (0×3+x+y)×2**+z=2×x+2×y+z(0×3+x+y)×2+z=2×x+2×y+z. Different programs, when executed may produce the same expressions; for example, executing [+w,×0**,+y,+x,×2**,+z,×1][+w,×0,+y,+x,×2,+z,×1] would also result in the expression 2×x+2×y+z2×x+2×y+z.

Bessie and Elsie each have programs of NN (1≤N≤20001≤N≤2000) instructions. They will interleave these programs to produce a new program of length 2N2N. Note that there are (2N)!N!×N!(2N)!N!×N! ways to do this, but not all such programs, when executed, will produce distinct expressions.

Count the number of distinct expressions that may be produced by executing Bessie and Elsie's interleaved program, modulo 109**+**7109+7.

Each input contains TT (1≤T≤101≤T≤10) test cases that should be solved independently. It is guaranteed that the sum of NN over all test cases does not exceed 20002000.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of the input contains TT, the number of test cases.The first line of each test case contains NN.

The second line of each test case contains Bessie's program, represented by a string of length NN. Each character is either a digit d∈**[0,9]**d∈[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. Note that their actual names are not provided, as they do not affect the answer.

OUTPUT FORMAT (print output to the terminal / stdout):

The number of distinct expressions that may be produced by executing Bessie and Elsie's interleaved programs, modulo 109**+**7109+7.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

1
3
9
9

For the first test case, the two possible interleaved programs are [×1,×0**][×1,×0] and [×0,×1]**[×0,×1]. These will both produce the expression 00 when executed.

For the second test case, executing an interleaving of [×1,×2**,+x][×1,×2,+x] and [+y,×0,×2**][+y,×0,×2] could produce one of the expressions 00, xx, or 2×x2×x.

SCORING:

• Input 2 satisfies N≤6N≤6.
• In inputs 3-5, the sum of all NN is at most 100100.
• In inputs 6-8, the sum of all NN is at most 500500.
• Inputs 9-16 satisfy no additional constraints.