Problem Description

You have an array $a$ of length $n$. At the beginning, all $a_i$ are $0$. You are given a target array $b$ of the same length $n$. Determine how many different ways there are such that, after performing the following operation several times, array $a$ can be turned into $b$.

• Choose two different indices $1\leq i<j\leq n$, and increase both $a_i$ and $a_j$ by $1$.

Two ways are considered different if and only if there exists some $x$ such that, in the $x$-th operation, the chosen pair of indices $(i,j)$ in one way is different from that in the other way.

Take the answer modulo $\bm{998244353}$.

Input Format

Read input from standard input.

The input consists of two lines.

The first line contains a positive integer $n$.

The second line contains $n$ positive integers, representing $b_1,b_2,\ldots,b_n$.

Output Format

Write output to standard output.

Output one line containing one positive integer, representing the number of ways to transform array $a$ into array $b$ using the operations, modulo $998244353$.

4
2 2 2 2

90

Hint

[Sample 1 Explanation]

The total number of ways is $6\times3+24\times3=90$.

[Sample 2]

See array/array2.in and array/array2.ans in the contestant files.

This sample satisfies the constraints of test points $6\sim8$.

[Sample 3]

See array/array3.in and array/array3.ans in the contestant files.

This sample satisfies the constraints of test points $12\sim14$.

[Sample 4]

See array/array4.in and array/array4.ans in the contestant files.

This sample satisfies the constraints of test points $15\sim18$.

[Sample 5]

See array/array5.in and array/array5.ans in the contestant files.

This sample satisfies the constraints of test points $19\sim20$.

[Sample 6]

See array/array6.in and array/array6.ans in the contestant files.

This sample satisfies the constraints of test points $21\sim22$.

[Sample 7]

See array/array7.in and array/array7.ans in the contestant files.

This sample satisfies the constraints of test points $23\sim25$.

[Constraints]

For $100\%$ of the data, $1\le n\le5~000$, $1\leq b_i\le3 \times 10^4$, and $\sum b_i\le3 \times 10^4$.

Translated by ChatGPT 5