P11152 [THUWC 2018] 七彩序列

来源：[https://www.gitlink.org.cn/thusaa/thuwc2018](https://www.gitlink.org.cn/thusaa/thuwc2018)。 2018 清华大学信息学冬季体验营（THUWC 2018）D2T2。$\texttt{5s,0.5G}$。

给出 $n$ 种颜色的小球若干，颜色的编号从 $1$ 至 $n$ ，第 $i$ 种颜色的小球共有 $a_i$ 个。小 $L$ 要把这些小球排成一个序列，使得**不**存在一个非空前缀或非空后缀是“整齐的”。这里我们称一个前缀或后缀是“整齐的”，当且仅当其中**所有 $n$ 个颜色**小球的出现次数相同。你的任务是计算本质不同的序列数目。 善良的 temporaryDO 给大家指出了一些必要的说明： 1. 一个序列长度为 $len$ 的**前缀**（后缀）指的是序列中最靠**左**（右）的 $len$ 个小球。而非空前缀或后缀指的即是 $len\neq 0$ 的前缀或后缀。 2. 对于一个小球的序列 $S$，令 $S_i$ 表示从左到右数的第 $i$ 个小球的颜色。我们认为两个小球序列 $S, T$ 本质不同，当且仅当存在一个位置 $i$ 使得 $S_i$ 不同于 $T_i$。 为了避免高精度，你只需要计算答案对 $998,244,353​$ 取模的结果即可。

从标准输入读入数据。 输入的第一行包含一个整数 $n$ ，表示颜色的种类数。 接下来一行包含 $n$ 个用空格隔开的整数，第 $i$ 个正整数为 $a_i$ ，表示第 $i$ 种颜色小球的数量。

输出到标准输出。 输出包含一行一个整数，表示本质不同的小球序列数目对 $998,244,353$ 取模的结果。

#### 样例 $1$ 解释 合法的两种方案分别为：`1 3 3 2` 和 `2 3 3 1`，显然，没有其他满足条件的序列。 ### 子任务 | 测试点编号 | $n=$ | $a_i\le$ | | :--: | :--: | :--: | | $1$ | $2$ | $500$ | | $2$ | $2$ | $2\times 10^5$ | | $3$ | $2$ | $2\times 10^5$ | | $4$ | $50$ | $2\times 10^3$ | | $5$ | $75$ | $2\times 10^3$ | | $6$ | $100$ | $2\times 10^3$ | | $7$ | $50$ | $10^5$ | | $8$ | $75$ | $1.5\times 10^5$ | | $9$ | $90$ | $1.75\times 10^5$ | | $10$ | $100$ | $2\times 10^5$ | 对于 $100\%$ 的数据，保证 $n \le 100$，所有 $a_i\le 200,000$。