Spanning Trees in a Hypercube Grid

Consider an n-dimensional grid representing a hypercube. The grid is defined by the integer parameters \(a_1,a_2,\dots,a_n\). In particular, there is a hypercube of size \((a_1-1)\times(a_2-1)\times\dots\times(a_n-1)\) with its lower‐left (minimum) corner at \((1,1,\dots,1)\) and its upper‐right (maximum) corner at \((a_1,a_2,\dots,a_n)\).

We then define an undirected graph whose vertices are the \(a_1\times a_2\times\dots\times a_n\) integer points \((x_1,x_2,\dots,x_n)\) satisfying \(1\le x_i\le a_i\) for \(1\le i\le n\). There is an edge between two distinct vertices \(U=(x_1,x_2,\dots,x_n)\) and \(V=(y_1,y_2,\dots,y_n)\) if and only if the segment connecting them is parallel to one of the edges of the hypercube. Equivalently, an edge exists if and only if exactly one coordinate differs between \(U\) and \(V\); that is, \[ \sum_{i=1}^{n}\mathbf{1}_{\{x_i=y_i\}} = n-1. \]

Your task is to calculate the number of spanning trees in this graph modulo \(998244353\). (A spanning tree is a tree that connects all vertices.)

inputFormat

The first line contains a single integer \(n\) (the dimension).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the size in each dimension.

outputFormat

Output a single integer, the number of spanning trees in the defined graph modulo \(998244353\).

sample

1
2

1