CF1188E.Problem from Red Panda

At Moscow Workshops ICPC team gets a balloon for each problem they solved first. Team MSU Red Panda got so many balloons that they didn't know how to spend them. So they came up with a problem with them.

There are several balloons, not more than $10^6$ in total, each one is colored in one of $k$ colors. We can perform the following operation: choose $k-1$ balloons such that they are of $k-1$ different colors, and recolor them all into remaining color. We can perform this operation any finite number of times (for example, we can only perform the operation if there are at least $k-1$ different colors among current balls).

How many different balloon configurations can we get? Only number of balloons of each color matters, configurations differing only by the order of balloons are counted as equal. As this number can be very large, output it modulo $998244353$.

在莫斯科 ICPC 训练营中，每支队伍每首次解出一道题便会获得一个气球。MSU Red Panda 队获得了大量气球，以至于他们不知如何处理这些气球，于是便基于气球设计了如下问题：

现有若干个气球，总数不超过 $10^6$ 个，每个气球被染成 $k$ 种颜色之一。我们可执行如下操作：选择 $k-1$ 个气球，要求它们恰好覆盖 $k-1$ 种互不相同的颜色，并将这 $k-1$ 个气球全部重新染成剩下的那一种（即未被选中的）颜色。我们可以执行该操作任意有限次（例如，仅当当前气球中至少包含 $k-1$ 种不同颜色时，才可执行该操作）。

问：通过上述操作，最多能得到多少种不同的气球配置？注意，仅考虑每种颜色的气球数量，即两个配置若仅气球顺序不同，则视为相同。由于答案可能非常大，请输出其对 $998244353$ 取模的结果。

The first line contains a single integer $k$ ($2 \le k \le 10^5$) —the number of colors.

The second line contains $k$ integers $a_1, a_2, \ldots, a_k$ ($0 \le a_i$) —initial configuration of balloons. $a_i$ is number of balloons of color $i$. The total number of balloons doesn't exceed $10^6$. In other words,

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

第一行包含一个整数 $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$。

Output number of possible configurations modulo $998244353$.

输出可能的配置数对 $998244353$ 取模的结果。

In the first example, there are $3$ configurations we can get: $[0, 1, 2]$, $[2, 0, 1]$, $[1, 2, 0]$.

In the second example, we can apply the operation not more than once, and possible configurations are: $[1, 1, 1, 1]$, $[0, 0, 0, 4]$, $[0, 0, 4, 0]$, $[0, 4, 0, 0]$, $[4, 0, 0, 0]$.

In the third example, we can't apply any operations, so the only achievable configuration is the starting one.

在第一个例子中，我们可以得到 $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]$。

在第三个例子中，我们无法执行任何操作，因此唯一可达的状态就是初始状态。