「KDOI-03」构造数组

你现在有一个长度为 $n$ 的数组 $a$。一开始，所有 $a_i$ 均为 $0$。给出一个同样长度为 $n$ 的目标数组 $b$。求有多少种方案，使得通过若干次以下操作，可以让 $a$ 数组变成 $b$。 * 选出两个**不同的**下标 $1\leq i<j\leq n$，并将 $a_i$ 和 $a_j$ 同时增加 $1$。 两种方案被称之为不同的，当且仅当存在一个 $x$ 使得一种方案中第 $x$ 次操作选择的两个下标 $(i,j)$ 与另一种方案中的不同。 **答案对 $\bm{998244353}$ 取模。** ## Input 从标准输入读入数据。 输入数据一共包含两行。 第一行包含一个正整数 $n$。 第二行包含 $n$ 个正整数，表示 $b_1,b_2,\ldots,b_n$。 ## Output 输出到标准输出。 输出一行一个正整数，表示将 $a$ 数组通过若干次操作变成 $b$ 数组的方案数对 $998244353$ 取模后的结果。 [samples] ## Note **【样例 1 解释】** | 种类编号 | 第一组 | 第二组 | 第三组 | 第四组 | 方案数 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | `1<->2` | `1<->2` | `3<->4` | `3<->4` | $\binom{4}{2}=6$ | | $2$ | `1<->3` | `1<->3` | `2<->4` | `2<->4` | $\binom{4}{2}=6$ | | $3$ | `1<->4` | `1<->4` | `2<->3` | `2<->3` | $\binom{4}{2}=6$ | | $4$ | `1<->2` | `1<->4` | `2<->3` | `3<->4` | $4!=24$ | | $5$ | `1<->2` | `1<->3` | `2<->4` | `3<->4` | $4!=24$ | | $6$ | `1<->3` | `1<->4` | `2<->3` | `2<->4` | $4!=24$ | 总方案数是 $6\times3+24\times3=90$。 **【样例 2】** 见选手文件中的 `array/array2.in` 与 `array/array2.ans`。 此样例满足测试点 $6\sim8$ 的限制。 **【样例 3】** 见选手文件中的 `array/array3.in` 与 `array/array3.ans`。 此样例满足测试点 $12\sim14$ 的限制。 **【样例 4】** 见选手文件中的 `array/array4.in` 与 `array/array4.ans`。 此样例满足测试点 $15\sim18$ 的限制。 **【样例 5】** 见选手文件中的 `array/array5.in` 与 `array/array5.ans`。 此样例满足测试点 $19\sim20$ 的限制。 **【样例 6】** 见选手文件中的 `array/array6.in` 与 `array/array6.ans`。 此样例满足测试点 $21\sim22$ 的限制。 **【样例 7】** 见选手文件中的 `array/array7.in` 与 `array/array7.ans`。 此样例满足测试点 $23\sim25$ 的限制。 *** **【数据范围】** 对于 $100\%$ 的数据，$1\le n\le5~000$，$1\leq b_i\le3 \times 10^4$，$\sum b_i\le3 \times 10^4$。 | 测试点编号 | $n$ | $\sum b_i$ | | :----------: | :----------: | :----------: | | $1$ | $\leq5~000$ | $\equiv 1\pmod 2$ | | $2\sim3$ | $=1$ | $\leq3 \times 10^4$ | | $4\sim5$ | $=2$ | $\leq3 \times 10^4$ | | $6\sim8$ | $\leq5$ | $\leq8$ | | $9\sim11$ | $\leq20$ | $=n$ | | $12\sim14$ | $\leq 5~000$ | $=n$ | | $15\sim18$ | $\leq16$ | $\leq16$ | | $19\sim20$ | $\le 700$ | $\le700$ | | $21\sim22$ | $\le 5~000$ | $\le5~000$ | | $23\sim25$ | $\le5~000$ | $\le3 \times 10^4$ |