说明

对于每个 $i = 1, 2, \ldots, N$，有 $A_i$ 个写有数字 $i$ 的球。这些球被放入一个盒子中并混合均匀。字符串变量 $s$ 初始由 $N$ 个 "0" 组成。球被一个一个地从盒子中取出（均匀随机且独立地抽取）。当抽到一个写有数字 $i$ 的球时，$s$ 的第 $i$ 个字符被改为 "1"（如果它原本已经是 "1"，则保持不变）。求在此过程中，存在某个时刻 $s$ 包含连续子串 "101" 的概率，结果对 $998,244,353$ 取模。

输入格式

输入包含一个单独的测试用例，格式如下：

$$\begin{aligned} &N \\ &A_1 \ A_2 \ \ldots \ A_N \end{aligned}$$

第一行包含一个介于 $1$ 到 $200,000$ 之间（含）的整数 $N$。第二行包含 $N$ 个正整数 $A_1, A_2, \ldots, A_N$。对于每个 $i$（$1 \leq i \leq N$），$A_i$ 表示写有数字 $i$ 的球的数量。它们满足 $\sum_{1 \leq i \leq N} A_i < 998,244,353$。

输出格式

输出一行，表示概率对 $998,244,353$ 取模的结果。

3
1 2 3

465847365

10
3 1 4 1 5 9 2 6 5 3

488186016

提示

注意

• 如何求概率对 $998,244,353$ 取模的结果
  • 可以证明，所求概率总是一个有理数。此外，本题的约束条件保证，如果将所求概率表示为最简分数 $\frac{y}{x}$，那么 $x$ 不能被 $998,244,353$ 整除。此时，存在唯一的 $0 \leq z < 998,244,353$ 使得 $y \equiv xz \pmod {998,244,353}$，请输出这个 $z$。

翻译由 DeepSeek V3.2 完成