E - Simple Speed Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

1 以上 N 以下の整数からなる整数列 B のうち、以下の条件を全て満たすものの個数を 998244353 で割ったあまりを出力してください。

  • 1 \le i \le N を満たす整数 i に対し、B の中に i はちょうど A_i 個存在する。
  • 1 \le i \le |B|-1 を満たす整数 i に対し、|B_i - B_{i+1}|=1 が成り立つ。

制約

  • 1 \le N \le 2 \times 10^5
  • 1 \le A_i \le 2 \times 10^5
  • 入力はすべて整数である。

入力

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

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

3
2 3 1

出力例 1

6

B としてあり得るものは、以下の 6 通りがあります。

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

よって、解は 6 です。

入力例 2

1
200000

出力例 2

0

条件を満たす B が存在しないこともあります。

入力例 3

6
12100 31602 41387 41498 31863 12250

出力例 3

750337372

Score : 800 points

Problem Statement

You are given a sequence of N positive integers: A=(A_1,A_2,\dots,A_N).

How many integer sequences B consisting of integers between 1 and N (inclusive) satisfy all of the following conditions? Print the count modulo 998244353.

  • For each integer i such that 1 \le i \le N, there are exactly A_i occurrences of i in B.
  • For each integer i such that 1 \le i \le |B|-1, it holds that |B_i - B_{i+1}|=1.

Constraints

  • 1 \le N \le 2 \times 10^5
  • 1 \le A_i \le 2 \times 10^5
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

3
2 3 1

Sample Output 1

6

B can be the following six sequences.

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

Thus, the answer is 6.

Sample Input 2

1
200000

Sample Output 2

0

There may be no sequence that satisfies the conditions.

Sample Input 3

6
12100 31602 41387 41498 31863 12250

Sample Output 3

750337372