题目描述

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

3
1 2 3

465847365

10
3 1 4 1 5 9 2 6 5 3

488186016

提示

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