分数: 450 点
问题陈述
给你一个正整数 N 和正整数序列 C=(C_1,C_2,\ldots,C_N) 长度 N.
查找给定正整数的模 M,满足以下所有条件的正整数序列的数量。
- 序列的所有元素都在 1 和 N,包括在内。
- 对于每个 i=1,2,\ldots,N,值 i 完全显示 序列中的 C_i 次。
T 给出了测试用例,因此请找到每个测试用例的答案。 M 是所有人共有的 T 测试用例。
约束
- 1\leq T\leq 10^5
- 2\leq M\leq 10^9
- 1\leq N
- 1\leq C_i
- \sum_{i=1}^N C_i\leq 5000
- 总和 一个输入文件中的 N 所有测试用例最多 3\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T M
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
的 树的 i- 第一个测试用例, \mathrm{case}_i,按以下格式给出:
N C_1 C_2 \ldots C_N
输出
输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 1000000000 2 2 2 5 1 1 1 1 1 6 1 2 3 4 5 6
示例输出 1
6 120 230379200
对于第一个测试用例,满足条件的序列是 (1,1,2,2),(1,2,1,2),(1,2,2,1),(2,1,1,2),(2,1,2,1),(2,2,1,1),这是六个序列。
示例输入 2
3 998244353 1 1 3 4 2 5 10 500 500 500 500 500 500 500 500 500 500
示例输出 2
1 6930 261233246