← 返回题目列表

AtCoder · abc425_e

H. 计数序列 2

中文机器翻译题面 查看原题

分数: 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