E - Strange Constraints Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

1 以上 N 以下の整数からなる長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

1 以上 N 以下の整数からなる長さ N の数列 B=(B_1,B_2,\ldots,B_N) のうち、全ての i=1,2,\ldots,N に対して以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。

  • B の中に含まれる i の個数は A_i 個以下
  • B の中に含まれる B_i の個数は A_i 個以下

制約

  • 1 \leq N \leq 500
  • 1 \leq A_i \leq N
  • 入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

3
1 2 3

出力例 1

10

条件を満たす数列は以下の 10 個です。

  • (1,2,2)
  • (1,2,3)
  • (1,3,2)
  • (1,3,3)
  • (2,1,3)
  • (2,3,1)
  • (2,3,3)
  • (3,1,2)
  • (3,2,1)
  • (3,2,2)

入力例 2

4
4 4 4 4

出力例 2

256

条件を満たす数列は、1 以上 4 以下の整数からなる長さ 4 の数列全てで、その個数は 4^4=256 個です。

入力例 3

5
1 1 1 1 1

出力例 3

120

条件を満たす数列は、(1,2,3,4,5) を並び替えて得られる数列全てで、その個数は 5!=120 個です。

入力例 4

14
6 5 14 3 6 7 3 11 11 2 3 7 8 10

出力例 4

628377683

個数を 998244353 で割ったあまりを出力してください。

Score : 700 points

Problem Statement

You are given a sequence of length N consisting of integers from 1 to N, A=(A_1,A_2,\ldots,A_N).

Find the number, modulo 998244353, of sequences of length N consisting of integers from 1 to N, B=(B_1,B_2,\ldots,B_N), that satisfy the following conditions for all i=1,2,\ldots,N.

  • The number of occurrences of i in B is at most A_i.
  • The number of occurrences of B_i in B is at most A_i.

Constraints

  • 1 \leq N \leq 500
  • 1 \leq A_i \leq N
  • All input values are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

3
1 2 3

Sample Output 1

10

The following 10 sequences satisfy the conditions:

  • (1,2,2)
  • (1,2,3)
  • (1,3,2)
  • (1,3,3)
  • (2,1,3)
  • (2,3,1)
  • (2,3,3)
  • (3,1,2)
  • (3,2,1)
  • (3,2,2)

Sample Input 2

4
4 4 4 4

Sample Output 2

256

All sequences of length 4 consisting of integers from 1 to 4 satisfy the conditions, and there are 4^4=256 such sequences.

Sample Input 3

5
1 1 1 1 1

Sample Output 3

120

All permutations of (1,2,3,4,5) satisfy the conditions, and there are 5!=120 such sequences.

Sample Input 4

14
6 5 14 3 6 7 3 11 11 2 3 7 8 10

Sample Output 4

628377683

Be sure to print the number modulo 998244353.