P6965: 配对编程
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
一个程序由一系列指令组成，每条指令都具有以下形式之一：
1.×d
，其中 d
是一个 [0,9] 范围内的一位数；
2.+s
，其中 s
是一个表示变量名称的字符串。一个程序中出现的所有的变量名均不相同。
程序执行的结果定义对表达式 0
依次应用每条指令后得到的表达式。例如，执行程序 [×3,+x,+y,×2,+z] 得到的结果是表达式 (0×3+x+y)×2+z=2×x+2×y+z。不同的程序执行后可能会得到相同的表达式；例如，执行[+w,×0,+y,+x,×2,+z,×1]
也会得到表达式 2×x+2×y+z。
Bessie
和 Elsie 各有一个 N（1≤N≤2000
）条指令的程序。他们将交错这些程序的指令以制造一个 2N
条指令的新程序。注意有 (2N)!/N!×N!
种方法可以做到这一点，但并非所有这样的程序在执行后都会得到不同的表达式。
计算执行 Bessie
和 Elsie 的交错程序可能得到的不同表达式的数量，对 10^9+7
取模。
每个测试用例包含 T
（1≤T≤10
）个需要独立求解的子测试用例。输入保证所有子测试用例中的 N
之和不超过 2000。
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 TT
，为子测试用例的数量。
每个子测试用例的第一行包含 N
。
每个子测试用例的第二行包含 Bessie
的程序，用一个长为 N 的字符串表示。每个字符是一个一位数 d∈[0,9]，表示类型 1
的一条指令，或字符 +，表示类型 2
的一条指令。
每个子测试用例的第三行包含 Elsie
的程序，格式与 Bessie 的程序相同。
在一个子测试用例中，所有指令内的变量名均不相同。注意在这里没有给出它们的实际名称，这是由于它们并不会影响答案。
【
输出格式】
（输出至终端 /
标准输出）：
输出通过执行 Bessie
和 Elsie 的交错程序可能得到的不同表达式的数量，对 10^9+7
取模。
【
输入样例】
：
4
1
0
1
3
12+
+02
3
0++
++9
4
5+++
+6+1
【
输出样例】
：
1
3
9
9
【样例说明】
对于第一个子测试用例，两个可以制造的交错程序为 [×1,×0]
和 [×0,×1]。它们执行后均会得到表达式 0
。
对于第二个子测试用例，执行 [×1,×2,+x]
和 [+y,×0,×2] 的交错程序可以得到表达式 0，x
和 2×x 之一。
【
测试点性质】
：
测试点 2
满足 N≤6。
测试点 3-5
中，所有 N 之和不超过 100。
测试点 6-8
中，所有 N 之和不超过 500。
测试点 9-16
没有额外限制。