重新分配石子

题目描述

有 $N$ 张编号为 1 到 $N$ 的盘子。盘子 $i$ 上放着 $a_i$ 个石子。另外还有一个空袋子。 你可以按任意顺序进行以下两种操作任意次(可以为 0 次):

1. 从每个放有 1 个及以上石子的盘子中各取出 1 个石子,将取出的石子放入袋子。
2. 从袋子中取出 $N$ 个石子,在每个盘子各放 1 个。注意,该操作仅在袋子中有 $N$ 个及以上石子时才能进行。

设操作结束后盘子 $i$ 上的石子数为 $b_i$。求可能得到的长度为 $N$ 的整数序列 $(b_1, b_2, \dots, b_N)$ 的数量对 $998244353$ 取模的结果。

输入格式

输入按以下格式从标准输入给出:

$N$
$a_1$ $a_2$ $\dots$ $a_N$

输出格式

输出可能得到的序列 $(b_1, b_2, \dots, b_N)$ 的数量对 $998244353$ 取模的结果。

样例

3
3 1 3

7

例如,通过以下步骤,$b$ 变为 $(2, 1, 2)$:

• 进行第 1 种操作,$b$ 变为 $(2, 0, 2)$。
• 进行第 1 种操作,$b$ 变为 $(1, 0, 1)$。
• 进行第 2 种操作,$b$ 变为 $(2, 1, 2)$。

操作后的 $b$ 可能为以下 7 种序列:

• $(0, 0, 0)$
• $(1, 0, 1)$
• $(1, 1, 1)$
• $(2, 0, 2)$
• $(2, 1, 2)$
• $(2, 2, 2)$
• $(3, 1, 3)$

1
0

1

操作后的 $b$ 可能为 $(0)$ 这 1 种。

5
1 3 5 7 9

36

10
766294629 440423913 59187619 725560240 585990756 965580535 623321125 550925213 122410708 549392044

666174028

数据范围

• $1 \le N \le 2 \times 10^5$
• $0 \le a_i \le 10^9$