Pair Programming

一个程序由一系列指令组成，每条指令都具有以下形式之一：

• \times d，其中 d 是一个 [0,9] 范围内的一位数；
• +s，其中 s 是一个表示变量名称的字符串。一个程序中出现的所有的变量名均不相同。

程序执行的结果定义对表达式 0 依次应用每条指令后得到的表达式。例如，执行程序 [\times 3,+x,+y,\times 2,+z] 得到的结果是表达式 (0\times 3+x+y)\times 2+z=2 \times x+2\times y+z。不同的程序执行后可能会得到相同的表达式；例如，执行 [+w,\times 0,+y,+x,\times 2,+z,\times 1] 也会得到表达式 2\times x+2\times y+z。

Bessie 和 Elsie 各有一个 N（1\le N\le 2000）条指令的程序。他们将交错这些程序的指令以制造一个 2N 条指令的新程序。注意有 \frac{(2N)!}{N!\times N!} 种方法可以做到这一点，但并非所有这样的程序在执行后都会得到不同的表达式。

计算执行 Bessie 和 Elsie 的交错程序可能得到的不同表达式的数量，对 10^9+7 取模。

每个测试用例包含 T（1\le T\le 10）个需要独立求解的子测试用例。输入保证所有子测试用例中的 N 之和不超过 2000。

输入的第一行包含 T，为子测试用例的数量。

每个子测试用例的第一行包含 N。

每个子测试用例的第二行包含 Bessie 的程序，用一个长为 N 的字符串表示。每个字符是一个一位数 d\in [0,9]，表示类型 1 的一条指令，或字符 +，表示类型 2 的一条指令。

每个子测试用例的第三行包含 Elsie 的程序，格式与 Bessie 的程序相同。

在一个子测试用例中，所有指令内的变量名均不相同。注意在这里没有给出它们的实际名称，这是由于它们并不会影响答案。

输出通过执行 Bessie 和 Elsie 的交错程序可能得到的不同表达式的数量，对 10^9+7 取模。

对于第一个子测试用例，两个可以制造的交错程序为 [\times 1, \times 0] 和 [\times 0,\times 1]。它们执行后均会得到表达式 0。

对于第二个子测试用例，执行 [\times 1,\times 2, +x] 和 [+y, \times 0,\times 2] 的交错程序可以得到表达式 0，x 和 2\times x 之一。

【测试点性质】

• 测试点 2 满足 N\le 6。
• 测试点 3-5 中，所有 N 之和不超过 100。
• 测试点 6-8 中，所有 N 之和不超过 500。
• 测试点 9-16 没有额外限制。

USACO22OPEN