在莫斯科研讨会上,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]$$$。
在第三个示例中,我们无法应用任何操作,因此唯一可实现的配置是起始配置。