配点 : $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 \leq N \leq 10^5$
• $0 \leq D_i \leq N-1$

入力

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

$N$

$D_1$ $D_2$ $...$ $D_N$

出力

答えを出力せよ。

4
0 1 1 2

2

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

4
1 1 1 1

0

7
0 3 2 1 2 2 1

24