問題文

頂点 $0, 1, \dots, N-1$ の $N$ 頂点からなる根付き木において，各頂点 $i$ の子の数が $d_i$ であるようなものの個数を $998244353$ で割った余りを求めてください．

ただし，木は以下の条件を満たしている必要があります．

• 条件: 葉でない（子の数が $1$ 以上の）任意の頂点 $v$ について，ある $v$ の子 $c$ が存在し，$v$ より番号の小さい $v$ の子孫は，すべて $c$ を先祖にもつ．

なお，頂点 $u$ が $v$ の先祖であるとは，$u=v$ であるか，あるいは $u$ が $v$ の親の先祖であることを指します．また，頂点 $u$ が $v$ の子孫であるとは，$v$ が $u$ の先祖であることを指します．

制約

• $2 \le N \le 2 \times 10^5$
• $0 \le d_i < N$
• $\sum_{i=0}^{N-1} d_i = N-1$
• 入力はすべて整数

入力

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

出力

条件を満たす根付き木の個数を $998244353$ で割った余りを出力せよ．

サンプル

3
1 1 0

2

以下の 2 つの木が条件を満たします．

1. 頂点 0 が根，0 の子が 1，1 の子が 2．
2. 頂点 1 が根，1 の子が 0，0 の子が 2．

例えば 2 のケースでは，頂点 1 について，子 $c=0$ を選ぶと，自分より小さい子孫 $\{0\}$ はすべて 0 の子孫であるため条件を満たします．