题目描述

你现在有一个长度为 $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}$ 取模。

输入格式

从标准输入读入数据。

输入数据一共包含两行。

第一行包含一个正整数 $n$。

第二行包含 $n$ 个正整数，表示 $b_1,b_2,\ldots,b_n$。

输出格式

输出到标准输出。

输出一行一个正整数，表示将 $a$ 数组通过若干次操作变成 $b$ 数组的方案数对 $998244353$ 取模后的结果。

4
2 2 2 2

90

提示

【样例 1 解释】

种类编号	第一组	第二组	第三组	第四组	方案数
$1$	1<->2		3<->4		$\binom{4}{2}=6$
$2$	1<->3		2<->4
$3$	1<->4	1<->4	2<->3	2<->3
$4$	1<->2			3<->4	$4!=24$
$5$		1<->3	2<->4
$6$	1<->3	1<->4	2<->3	2<->4

总方案数是 $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$
$6\sim8$	$\leq5$	$\leq8$
$9\sim11$	$\leq20$	$=n$
$12\sim14$	$\leq 5~000$
$15\sim18$	$\leq16$
$19\sim20$	$\le 700$	$\le700$
$21\sim22$	$\le 5~000$	$\le5~000$
$23\sim25$	$\le5~000$	$\le3 \times 10^4$