题目描述

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

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

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

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

输入格式

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

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

答えを出力せよ。

题目大意

给出一个大小为 $N$ 的可重集 $A=\lbrace\ A_1,A_2,\dots,A_N\ \rbrace$。

你可以执行若干次如下操作（也可以不执行）。

• 将两个 $x$ 合并成一个 $x+1$。

输出最终可能的集合个数对 $998244353$ 取模的结果。

4
1 1 2 4

3

5
1 2 3 4 5

1

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

66

提示

制約

• $1\ \le\ N\ \le\ 2\ \times\ 10^5$
• $1\ \le\ A_i\ \le\ 2\ \times\ 10^5$

Sample Explanation 1

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