30370번 - Gacha 101 다국어

문제

For each $i = 1, 2, \dots, 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.

$N$

$A_1$ $A_2$ $\dots$ $A_N$

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, \dots , A_N$. For each $i$ (1ドル \le i \le N$), $A_i$ represents the number of balls $i$ written. And they satisfy $\sum_{1 \le i \le N}{A_i} < 998,244円,353円$.

출력

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

제한

노트

• 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ドル \le z < 998,244円,353円$ such that $y \equiv xz \pmod{998,244円,353円},ドル so report this $z$.