题目描述

给定一个由正整数组成的 $N$ 元素多重集 $A=\lbrace A_1,A_2,\dots,A_N \rbrace$。

你可以任意次数（也可以不进行操作）重复以下操作：

• 选择一个在 $A$ 中出现次数不少于 $2$ 的正整数 $x$。从 $A$ 中删除 $2$ 个 $x$，并向 $A$ 中添加 $1$ 个 $x+1$。

请你求出最终可能得到的 $A$ 的不同多重集的个数，并对 $998244353$ 取模后输出。

输入格式

输入以以下格式从标准输入给出。

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

输出格式

输出答案。

样例 1

输入

4
1 1 2 4

输出

3

样例 2

输入

5
1 2 3 4 5

输出

1

样例 3

输入

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

输出

66

说明/提示

限制条件

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

样例解释 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$ 中删除 $2$ 个 $1$，添加 $1$ 个 $2$，此时 $A=\lbrace 2,2,4 \rbrace$。
• 选择 $x=2$，从 $A$ 中删除 $2$ 个 $2$，添加 $1$ 个 $3$，此时 $A=\lbrace 3,4 \rbrace$。

由 ChatGPT 4.1 翻译