Problem Description

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$.

Input Format

The first line contains a positive integer $n$.

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

Output Format

Output the answer modulo $998244353$.

1
5

125

5
2 3 4 5 6

676736091

Hint

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