B - Counting of Trees Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 要素からなる整数列 D_1,...,D_N が与えられます。頂点に 1 から N の番号が付けられた N 頂点からなる木であって、 以下の条件をみたすものの個数を 998244353 で割ったあまりを求めてください。

  • 1 以上 N 以下の任意の整数 i に対して、頂点 1 と頂点 i の距離が D_i である。

注記

  • N 頂点の木とは N 頂点 N-1 辺からなる連結無向グラフのことであり、2 頂点の距離とは一方から他方への最短路に用いられる辺の個数を指します。
  • 2 つの木が異なるとは、ある 2 頂点 x, y が存在して、x と y の間に一方の木では辺が存在し、 もう一方の木では辺が存在しないことを指します。

制約

  • 1 ≦ N ≦ 10^5
  • 0 ≦ D_i ≦ N-1

入力

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

N
D_1 D_2 ... D_N

出力

答えを出力せよ。

入力例 1

4
0 1 1 2

出力例 1

2

例えば、(1,2), (1,3), (2,4) の間に辺があるような木が条件をみたします。

入力例 2

4
1 1 1 1

出力例 2

0

入力例 3

7
0 3 2 1 2 2 1

出力例 3

24

Score : 300 points

Problem Statement

Given is an integer sequence D_1,...,D_N of N elements. Find the number, modulo 998244353, of trees with N vertices numbered 1 to N that satisfy the following condition:

  • For every integer i from 1 to N, the distance between Vertex 1 and Vertex i is D_i.

Notes

  • A tree of N vertices is a connected undirected graph with N vertices and N-1 edges, and the distance between two vertices are the number of edges in the shortest path between them.
  • Two trees are considered different if and only if there are two vertices x and y such that there is an edge between x and y in one of those trees and not in the other.

Constraints

  • 1 \leq N \leq 10^5
  • 0 \leq D_i \leq N-1

Input

Input is given from Standard Input in the following format:

N
D_1 D_2 ... D_N

Output

Print the answer.

Sample Input 1

4
0 1 1 2

Sample Output 1

2

For example, a tree with edges (1,2), (1,3), and (2,4) satisfies the condition.

Sample Input 2

4
1 1 1 1

Sample Output 2

0

Sample Input 3

7
0 3 2 1 2 2 1

Sample Output 3

24