P15722 [JAG 2023 Summer Camp #3] Gacha 101

For each $i = 1, 2, \ldots, N$, there are $A_i$ balls with $i$ written on them. These are put into a box and mixed up. The string variable $s$ consists of initially $N$ "0"s. Balls are taken out of the box one by one (uniformly at random and independently). When a ball with $i$ written on it is drawn, the $i$-th character of $s$ is changed to "1" (it remains unchanged if it was already "1"). Find the probability, modulo $998,244,353$, of having a point during this process that $s$ contains "101" as a contiguous substring.

The input consists of a single test case of the following format. $$ \begin{aligned} &N \\ &A_1 \ A_2 \ \ldots \ A_N \end{aligned} $$ The first line consists of an integer $N$ between $1$ and $200,000$, inclusive. The second line consists of $N$ positive integers $A_1, A_2, \ldots, A_N$. For each $i$ ($1 \leq i \leq N$), $A_i$ represents the number of balls $i$ written. And they satisfy $\sum_{1 \leq i \leq N} A_i < 998,244,353$.

Output in a line the probability modulo $998,244,353$.

### Note - How to find the probability modulo $998,244,353$ - It can be proved that the sought probability is always a rational number. Additionally, the constraints of this problem guarantee that if the sought probability is represented as an irreducible fraction $\frac{y}{x}$, then $x$ is not divisible by $998,244,353$. Here, there is a unique $0 \leq z < 998,244,353$ such that $y \equiv xz \pmod {998,244,353}$, so report this $z$.