P8863 "KDOI-03" Constructing an Array

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

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

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

**[Sample 1 Explanation]** | Type ID | First group | Second group | Third group | Fourth group | Number of ways | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | `12` | `12` | `34` | `34` | $\binom{4}{2}=6$ | | $2$ | `13` | `13` | `24` | `24` | $\binom{4}{2}=6$ | | $3$ | `14` | `14` | `23` | `23` | $\binom{4}{2}=6$ | | $4$ | `12` | `14` | `23` | `34` | $4!=24$ | | $5$ | `12` | `13` | `24` | `34` | $4!=24$ | | $6$ | `13` | `14` | `23` | `24` | $4!=24$ | 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$. | Test point ID | $n$ | $\sum b_i$ | | :----------: | :----------: | :----------: | | $1$ | $\leq5~000$ | $\equiv 1\pmod 2$ | | $2\sim3$ | $=1$ | $\leq3 \times 10^4$ | | $4\sim5$ | $=2$ | $\leq3 \times 10^4$ | | $6\sim8$ | $\leq5$ | $\leq8$ | | $9\sim11$ | $\leq20$ | $=n$ | | $12\sim14$ | $\leq 5~000$ | $=n$ | | $15\sim18$ | $\leq16$ | $\leq16$ | | $19\sim20$ | $\le 700$ | $\le700$ | | $21\sim22$ | $\le 5~000$ | $\le5~000$ | | $23\sim25$ | $\le5~000$ | $\le3 \times 10^4$ | Translated by ChatGPT 5