Triangulation of a Subdivided Convex Polygon

Given a convex polygon with (n) sides, each side (i) in clockwise order is divided into (a_i) equal segments by adding (a_i-1) extra points on that side. You are to count the number of triangulations of the resulting figure subject to the following conditions:

1. You may add chords (line segments connecting two vertices) between any two vertices. However, any two added chords may only intersect at their endpoints.
2. An added chord must not coincide with any side of the original polygon.
3. After adding chords, the interior of the polygon is partitioned into faces, and each face must be a triangle. Note that a triangle’s edge may contain extra vertices that lie on an original polygon side.

It can be shown that the number of valid triangulations is given by:

[ \text{Answer} = C_{n-2} \times \prod_{i=1}^{n} C_{a_i-1}, ]

where the (k)th Catalan number (C_{k}) is defined in (\LaTeX) as:

[ C_{k} = \frac{1}{k+1}\binom{2k}{k}. ]

Your task is to compute the number of such triangulations modulo 998244353.

inputFormat

The input consists of two lines. The first line contains a single integer (n) (with (n \ge 3)), representing the number of sides of the convex polygon. The second line contains (n) integers (a_1, a_2, \ldots, a_n) (each (a_i \ge 1)), where the (i)th side is subdivided into (a_i) equal segments.

outputFormat

Output a single integer, the number of valid triangulations modulo 998244353.

sample

3
1 1 1

1