题目描述

你得到一个包含 $N$ 个正整数的多重集合：$A=\\lbrace A_1,A_2,\\dots,A_N \\rbrace$。

你可以重复任意次数（可能为零）执行以下操作。

• 选择在 $A$ 中至少出现两次的正整数 $x$。从 $A$ 中删除两次出现的 $x$，并将 $x+1$ 添加一次到 $A$ 中。

找到最终可能的多重集合 $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$ 中的一个。

你可以通过以下方式得到 $A = \\lbrace 3,4 \\rbrace$。

• 选择 $x = 1$。从 $A$ 中删除两个 $1$，并添加一个 $2$，使得 $A=\\lbrace 2,2,4 \\rbrace$。
• 选择 $x = 2$。从 $A$ 中删除两个 $2$，并添加一个 $3$，使得 $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