← 返回题目列表

Codeforces · 1188/E

E. 小熊猫的问题

中文机器翻译题面 查看原题

在莫斯科研讨会上,ICPC 团队为他们首先解决的每个问题获得一个气球。密歇根州立大学红熊猫队得到了很多气球,他们不知道如何花掉它们。所以他们想出了一个问题。

有几个气球,总共不超过 $$$10^6$$$,每个气球都涂有 $$$k$$$ 颜色之一。我们可以执行以下操作:选择$$$k-1$$$气球,使其具有$$$k-1$$$不同颜色,并将它们全部重新着色为剩余颜色。我们可以执行此操作任意有限次数(例如,只有当前球之间至少有 $$$k-1$$$ 不同颜色时我们才能执行该操作)。

我们可以获得多少种不同的气球配置?仅每种颜色的气球数量很重要,仅气球顺序不同的配置被视为相等。由于这个数字可能非常大,因此输出它对 $$$998244353$$$ 取模。

输入

第一行包含一个整数 $$$k$$$ ($$$2 \le k \le 10^5$$$) — 颜色数量。

第二行包含 $$$k$$$ 整数 $$$a_1, a_2, \ldots, a_k$$$ ($$$0 \le a_i$$$) - 气球的初始配置。 $$$a_i$$$ 是颜色 $$$i$$$ 的气球数量。气球总数不超过$$$10^6$$$。换句话说,

$$$a_1 + a_2 + a_3 + \ldots + a_k \le 10^6$$$。

输出

输出可能配置的数量,以 $$$998244353$$$ 为模。

示例

输入 #1

3
0 1 2

输出 #1

3

输入 #2

4
1 1 1 1

输出 #2

5

输入 #3

5
0 0 1 2 3

输出 #3

1

输入#4

3
2 2 8

输出#4

31

注意

在第一个示例中,我们可以获得$$$3$$$配置:$$$[0, 1, 2]$$$,$$$[2, 0, 1]$$$,$$$[1, 2, 0]$$$。

在第二个示例中,我们只能应用该操作一次,可能的配置为: $$$[1, 1, 1, 1]$$$, $$$[0, 0, 0, 4]$$$, $$$[0, 0, 4, 0]$$$, $$$[0, 4, 0, 0]$$$, $$$[4, 0, 0, 0]$$$。

在第三个示例中,我们无法应用任何操作,因此唯一可实现的配置是起始配置。