P9005 [RC-07] Super Hypercube.

There is an $n$-dimensional hypercube of size $(a_1-1)\times (a_2-1)\times \dots \times (a_n-1)$. The coordinates of the lower-left corner are $(1,1,\dots,1)$, and the coordinates of the upper-right corner are $(a_1,a_2,\dots,a_n)$. Consider an undirected graph with $a_1\times a_2\times \dots \times a_n$ labeled vertices. The label of a vertex is $(x_1,\dots,x_n)\ (1\le x_i\le a_i)$, and each vertex corresponds to an integer lattice point inside or on the boundary of the hypercube. For a pair of vertices $(U,V)\ (U=(x_1,\dots,x_n),V=(y_1,\dots,y_n))$ in the graph, there is an edge between them if and only if $UV$ is parallel to an edge of the hypercube. In other words, $\sum_{1\le i\le n}[x_i=y_i]=n-1$. Compute the number of spanning trees of this graph modulo $998244353$.

The first line contains a positive integer $n$. The next line contains $n$ positive integers $a_1,a_2,\dots,a_n$.

Output the answer modulo $998244353$.

All testdata satisfy: $1\le n\le 100$, $2\le a_i\le 5000$. - Subtask $1$ ($5$ points): $n=1$. - Subtask $2$ ($5$ points): $n\le 3,\prod a_i\le 500$. - Subtask $3$ ($10$ points): $n=2$. - Subtask $4$ ($80$ points): No special constraints. Translated by ChatGPT 5