配点 : $500$ 点

問題文

正整数からなる $N$ 要素の多重集合 $A=\lbrace A_1,A_2,\dots,A_N \rbrace$ が与えられます。

あなたは、以下の操作を好きな回数 ( $0$ 回でもよい) 繰り返すことが出来ます。

• $A$ に $2$ 個以上含まれる正整数 $x$ を選ぶ。$A$ から $x$ を $2$ 個削除し、$A$ に $x+1$ を $1$ 個加える。

最終的な $A$ としてあり得るものの個数を $998244353$ で割ったあまりを求めてください。

制約

• $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$

出力

答えを出力せよ。

4
1 1 2 4

3

最終的な $A$ としてあり得るものは、$\lbrace 1,1,2,4 \rbrace,\lbrace 2,2,4 \rbrace,\lbrace 3,4 \rbrace$ の $3$ 個があります。

$\lbrace 3,4 \rbrace$ は以下のようにして作ることが出来ます。

• $x$ として $1$ を選ぶ。$A$ から $1$ を $2$ 個削除し、$2$ を $1$ 個加える。$A=\lbrace 2,2,4 \rbrace$ となる。
• $x$ として $2$ を選ぶ。$A$ から $2$ を $2$ 個削除し、$3$ を $1$ 個加える。$A=\lbrace 3,4 \rbrace$ となる。

5
1 2 3 4 5

1

13
3 1 4 1 5 9 2 6 5 3 5 8 9

66