CF1188E Problem from Red Panda

有不超过 $10^6$ 个气球，每个气球被染上了 $k$ 种颜色中的一种，颜色用 $1 \sim k$ 进行标号。你可以选择做若干次（可以不做）以下操作： - 选择一个颜色 $i \in [1,k]$，如果其他的 $k-1$ 种颜色的气球每种都至少有一个，则在每一种其他颜色中选出一个气球染成颜色 $i$。 现在给出初始每种颜色的气球数量，你需要求出通过做若干次操作能够得到的不同的气球组合方案数对 $998244353$ 取模。两种气球组合方案不同当且仅当其中存在一种颜色满足在两种方案中染上这个颜色的气球数量不同。

第一行一个整数 $k$ 表示颜色数量，接下来一行 $k$ 个非负整数 $a_1,a_2,...,a_k$ 分别表示颜色 $1,2,...,k$ 的气球的初始数量。

一行一个整数表示方案数 $\bmod\ 998244353$。

$2 \leq k \leq 10^5 , a_i \geq 0,\sum\limits_{i=1}^k a_i \leq 10^6$