考虑标有整数的球。对于每个 $i = 1, 2, \dots, N$，有 $A_i$ 个标有整数 $i$ 的球。

将这些球放入一个盒子中并混合。考虑一个二进制字符串 $s$。初始时，$s$ 由 $N$ 个数字“0”组成。然后，我们逐个从盒子中取出球（均匀随机且独立），并将它们留在盒子外。当我们取出标有整数 $i$ 的球时，$s$ 的第 $i$ 个字符变为“1”（如果已经是“1”则保持不变）。

求在这一过程中，某个时刻 $s$ 包含“101”作为连续子串的概率，并将其对质数 $998\,244\,353$ 取模后输出。

形式化地，可以证明所求概率是一个有理数。此外，本题的约束条件保证，如果该数表示为不可约分数 $\frac{y}{x}$，则 $x$ 不能被 $998\,244\,353$ 整除。因此存在唯一的 $q$，满足 $0 \le q < 998\,244\,353$ 且 $y \equiv x \cdot q \pmod{998\,244\,353}$。你需要求出并打印这个值 $q$。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 2 \cdot 10^5$)。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$：其中 $A_i$ 是标有整数 $i$ 的球的数量（所有 $A_i > 0$ 且 $\sum_{i=1}^N A_i < 998\,244\,353$）。

输出格式

输出所求概率对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

3
1 2 3

样例输出 1

465847365

样例输入 2

10
3 1 4 1 5 9 2 6 5 3

样例输出 2

488186016