袜子 3

题目描述

高桥君的抽屉里放着各种颜色的袜子。 袜子的颜色用 $1$ 到 $N$ 的整数表示,颜色 $i$ 的袜子有 $A_i\ (\ge 2)$ 只。

他打算通过执行以下操作来决定今天穿的袜子:

从抽屉中随机且等概率地一次取出一只袜子,不断重复,直到已经取出的袜子中能凑出两只同颜色的袜子为止。 取出的袜子不再放回抽屉。

求高桥君从抽屉中取出袜子次数的期望值对 $998244353$ 取模的值。

期望值对 $998244353$ 取模的方法

可以证明,所求期望值一定是有理数。 此外,本问题的约束保证了将期望值表示为既约分数 $\frac{y}{x}$ 时,$x$ 不会被 $998244353$ 整除。 此时,存在唯一的整数 $z$($0 \le z \le 998244352$)满足 $xz \equiv y \pmod{998244353}$。求出这个 $z$。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案。

样例

2
2 2

665496238

例如,操作可能按如下方式进行:

从抽屉中取出一只颜色 $1$ 的袜子。抽屉中还剩一只颜色 $1$ 的袜子和两只颜色 $2$ 的袜子。

从抽屉中取出一只颜色 $2$ 的袜子。抽屉中还剩颜色 $1$、颜色 $2$ 的袜子各一只。

从抽屉中取出一只颜色 $1$ 的袜子。此时取出的袜子中,颜色 $1$ 的有两只、颜色 $2$ 的有一只,可以凑出颜色 $1$ 的袜子一对,操作结束。

在这个例子中,高桥君从抽屉中取出了 $3$ 次袜子。

高桥君从抽屉中取出袜子的次数以 $\frac{2}{3}$ 的概率为 $3$ 次,以 $\frac{1}{3}$ 的概率为 $2$ 次,因此所求期望值为 $3 \times \frac{2}{3} + 2 \times \frac{1}{3} = \frac{8}{3} \equiv 665496238 \pmod {998244353}$。

1
352

2

6
1796 905 2768 253 2713 1448

887165507

数据范围

• $1 \le N \le 3 \times 10^5$
• $2 \le A_i \le 3000$
• 输入中的所有值均为整数