問題文

正整数からなる $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$

出力

答えを出力せよ。

入力例 1

4
1 1 2 4

出力例 1

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$ となる。

入力例 2

5
1 2 3 4 5

出力例 2

1

入力例 3

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

出力例 3

66