Array Transformation by Pair Increments

We are given an integer n and two arrays of length n: an initial array a (with all entries equal to 0) and a target array b. In one operation, you may choose two different indices i and j with \(1\le i<j\le n\) and increase both \(a_i\) and \(a_j\) by 1. A sequence of operations is allowed (the number of operations can be zero or more) and two sequences are considered different if there exists an index \(x\) such that the pair chosen in the \(x\)th operation differ.

Determine the number of sequences of operations that transform array \(a\) into \(b\). Since each operation increases the sum of the array by 2, a necessary condition is that

[ \sum_{i=1}^{n} b_i \equiv 0 \pmod{2}. ]

If we let \(T=\frac{1}{2}\sum_{i=1}^{n}b_i\) be the total number of operations, then clearly each index \(i\) is chosen in exactly \(b_i\) operations. In particular, we must have \(b_i\le T\) for all \(i\). The answer is defined modulo \(998244353\).

The answer can be written in a combinatorial form. In fact, note that choosing an ordered sequence of \(T\) operations (each operation is an unordered pair \((i,j)\)) so that every index \(i\) appears exactly \(b_i\) times is equivalent to filling a \(0/1\) incidence matrix with \(T\) columns (operations) and n rows (indices) such that each column has exactly two 1's and the sum of the entries in the \(i\)th row is \(b_i\). One may show that the answer is given by

[ \text{Answer} = T!\times \Bigl[\text{coefficient of }x_1^{b_1}x_2^{b_2}\cdots x_n^{b_n}\text{ in }\Bigl(\sum_{1\le i<j\le n}x_ix_j\Bigr)^T\Bigr] \pmod{998244353}. ]

For this problem, you are required to compute the number of valid sequences modulo \(998244353\). You can assume that the constraints are such that a solution using a recursive dynamic programming approach with memoization is feasible.

inputFormat

The first line contains a single integer n (the length of the arrays).

The second line contains n space‐separated nonnegative integers \(b_1,b_2,\dots,b_n\), representing the target array.

outputFormat

Output a single integer, the number of ways to transform the initial array into the target array modulo \(998244353\).

sample

2
1 1

1