Logo Infinity Online Judge

InfOJ

时间限制:1 s 空间限制:512 MB

#235. 超超立方体

统计

题目描述

有一个 $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

样例输入 #1

1
5

样例输出 #1

125

样例 #2

样例输入 #2

5
2 3 4 5 6

样例输出 #2

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$ 分):无特殊限制。