题目描述

有一个 $n$ 维 $(a_1-1)\times (a_2-1)\times \dots \times (a_n-1)$ 超立方体。左下角坐标为 $(1,1,\dots,1)$，右上角坐标为 $(a_1,a_2,\dots,a_n)$。

考虑一个无向图，有 $a_1\times a_2\times \dots \times a_n$ 个有标号的结点。结点的标号分别为 $(x_1,\dots,x_n)\ (1\le x_i\le a_i)$，每个节点对应超立方体内部或者边界上一个整点。对于一对图上的顶点 $(U,V)\ (U=(x_1,\dots,x_n),V=(y_1,\dots,y_n))$，它们之间有边相连当且仅当 $UV$ 平行于超立方体的一条棱。换句话说，也就是 $\sum_{1\le i\le n}[x_i=y_i]=n-1$。

计算该图生成树个数对 $998244353$ 取模的结果。

输入格式

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

接下来一行 $n$ 个正整数 $a_1,a_2,\dots,a_n$。

输出格式

输出答案对 $998244353$ 取模的结果。

1
5

125

5
2 3 4 5 6

676736091

提示

所有数据均满足：$1\le n\le 100$，$2\le a_i\le 5000$。

• 子任务 $1$（$5$ 分）：$n=1$。
• 子任务 $2$（$5$ 分）：$n\le 3,\prod a_i\le 500$。
• 子任务 $3$（$10$ 分）：$n=2$。
• 子任务 $4$（$80$ 分）：无特殊限制。