7474: USACO 2022 US Open Contest, Gold —— T2 Pair Programming
[Creator : ]
Description
一个程序由一系列指令组成，每条指令都具有以下形式之一：
Bessie 和 Elsie 各有一个 $N\ (1≤N≤2000)$ 条指令的程序。他们将交错这些程序的指令以制造一个 $2N$ 条指令的新程序。注意有 $\frac{(2N)!}{N!×N!}$ 种方法可以做到这一点，但并非所有这样的程序在执行后都会得到不同的表达式。
计算执行 Bessie 和 Elsie 的交错程序可能得到的不同表达式的数量，对 $10^9+7$ 取模。
每个测试用例包含 $T\ (1≤T≤10)$ 个需要独立求解的子测试用例。输入保证所有子测试用例中的 $N$ 之和不超过 $2000$。
- $×d$，其中 $d$ 是一个 $[0,9]$ 范围内的一位数；
- $+s$，其中 $s$ 是一个表示变量名称的字符串。一个程序中出现的所有的变量名均不相同。
Bessie 和 Elsie 各有一个 $N\ (1≤N≤2000)$ 条指令的程序。他们将交错这些程序的指令以制造一个 $2N$ 条指令的新程序。注意有 $\frac{(2N)!}{N!×N!}$ 种方法可以做到这一点，但并非所有这样的程序在执行后都会得到不同的表达式。
计算执行 Bessie 和 Elsie 的交错程序可能得到的不同表达式的数量，对 $10^9+7$ 取模。
每个测试用例包含 $T\ (1≤T≤10)$ 个需要独立求解的子测试用例。输入保证所有子测试用例中的 $N$ 之和不超过 $2000$。
Input
输入的第一行包含 $T$，为子测试用例的数量。 每个子测试用例的第一行包含 $N$。
每个子测试用例的第二行包含 Bessie 的程序，用一个长为 $N$ 的字符串表示。每个字符是一个一位数 $d \in [0,9]$，表示类型 $1$ 的一条指令，或字符 $+$，表示类型 $2$ 的一条指令。
每个子测试用例的第三行包含 Elsie 的程序，格式与 Bessie 的程序相同。
在一个子测试用例中，所有指令内的变量名均不相同。注意在这里没有给出它们的实际名称，这是由于它们并不会影响答案。
每个子测试用例的第二行包含 Bessie 的程序，用一个长为 $N$ 的字符串表示。每个字符是一个一位数 $d \in [0,9]$，表示类型 $1$ 的一条指令，或字符 $+$，表示类型 $2$ 的一条指令。
每个子测试用例的第三行包含 Elsie 的程序，格式与 Bessie 的程序相同。
在一个子测试用例中，所有指令内的变量名均不相同。注意在这里没有给出它们的实际名称，这是由于它们并不会影响答案。
Output
输出通过执行 Bessie 和 Elsie 的交错程序可能得到的不同表达式的数量，对 $10^9+7$ 取模。
Constraints
测试点 2 满足 $N≤6$。
测试点 3-5 中，所有 $N$ 之和不超过 $100$。
测试点 6-8 中，所有 $N$ 之和不超过 $500$。
测试点 9-16 没有额外限制。
测试点 3-5 中，所有 $N$ 之和不超过 $100$。
测试点 6-8 中，所有 $N$ 之和不超过 $500$。
测试点 9-16 没有额外限制。
Sample 1 Input
4
1
0
1
3
12+
+02
3
0++
++9
4
5+++
+6+1
Sample 1 Output
1
3
9
9
对于第一个子测试用例，两个可以制造的交错程序为 $[×1,×0]$ 和 $[×0,×1]$。它们执行后均会得到表达式 $0$。
对于第二个子测试用例，执行 $[×1,×2,+x]$ 和 $[+y,×0,×2]$ 的交错程序可以得到表达式 $0$，$x$ 和 $2×x$ 之一。
对于第二个子测试用例，执行 $[×1,×2,+x]$ 和 $[+y,×0,×2]$ 的交错程序可以得到表达式 $0$，$x$ 和 $2×x$ 之一。