P8273 [USACO22OPEN] Pair Programming G
题目背景
由于题目数据问题,在本题中,你**无需考虑**非平凡的(都有 0 或者只差若干个 1 或者仅顺序不同时称为平凡的)、两组不同的数乘积一样的情况,例如 $t\times2\times3=t\times6$;或者,你应当把题面中的 $\times 2,3,4,5,6,7,8,9$ 分别视为 $\times 2,3,5,7,11,13,17,19$ 处理。
题目描述
一个程序由一系列指令组成,每条指令都具有以下形式之一:
- $\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$。
输入格式
无
输出格式
无
说明/提示
【样例解释】
对于第一个子测试用例,两个可以制造的交错程序为 $[\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 没有额外限制。