E - Count Sequences 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

正整数 N および長さ N の正整数列 C=(C_1,C_2,\ldots,C_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,1,2,2),(1,2,1,2),(1,2,2,1),(2,1,1,2),(2,1,2,1),(2,2,1,1) の 6 個です。

入力例 2

3 998244353
1
1
3
4 2 5
10
500 500 500 500 500 500 500 500 500 500

出力例 2

1
6930
261233246

Score : 450 points

Problem Statement

You are given a positive integer N and a sequence of positive integers C=(C_1,C_2,\ldots,C_N) of length N.

Find, modulo a given positive integer M, the number of sequences of positive integers that satisfy all of the following conditions.

  • All elements of the sequence are between 1 and N, inclusive.
  • For each i=1,2,\ldots,N, the value i appears exactly C_i times in the sequence.

T test cases are given, so find the answer for each. M is common to all T test cases.

Constraints

  • 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
  • The sum of N over all test cases is at most 3\times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T M
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

The i-th test case, \mathrm{case}_i, is given in the following format:

N
C_1 C_2 \ldots C_N

Output

Output T lines. The i-th line should contain the answer for the i-th test case.

Sample Input 1

3 1000000000
2
2 2
5
1 1 1 1 1
6
1 2 3 4 5 6

Sample Output 1

6
120
230379200

For the first test case, the sequences that satisfy the conditions are (1,1,2,2),(1,2,1,2),(1,2,2,1),(2,1,1,2),(2,1,2,1),(2,2,1,1), which is six sequences.

Sample Input 2

3 998244353
1
1
3
4 2 5
10
500 500 500 500 500 500 500 500 500 500

Sample Output 2

1
6930
261233246