题目背景

来源：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$ 取模的结果。

3
1 1 2

2

5
5 6 7 8 9

322192262

提示

样例 $1$ 解释

合法的两种方案分别为：1 3 3 2 和 2 3 3 1，显然，没有其他满足条件的序列。

子任务

对于 $100\%$ 的数据，保证 $n \le 100$，所有 $a_i\le 200,000$。