Score: $600$ points

问题陈述

高桥在他的抽屉里有各种颜色的袜子。袜子的颜色由整数 $1$ 到 $N$ 表示，颜色 $i$ 的袜子有 $A_i\ (\geq 2)$ 只。

他即将通过执行以下操作来选择今天要穿哪双袜子：

• 继续从抽屉中随机抽取一只袜子，每次抽取的概率相等，直到他能够从已经抽取的袜子中配成一对同色的袜子。一旦抽取了一只袜子，它将不会被放回抽屉。

找出他必须从抽屉中抽取袜子的次数的期望值，模 $998244353$。

寻找模 $998244353$ 的期望值意味着什么？可以证明所求的期望值总是有理数。此外，这个问题的约束条件保证如果期望值表示为不可约分数 $\frac{y}{x}$，那么 $x$ 不能被 $998244353$ 整除。在这里，存在一个唯一的整数 $z$，介于 $0$ 和 $998244352$（包括 $0$ 和 $998244352$），使得 $xz \equiv y \pmod{998244353}$。找出这个 $z$。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

Takahashi has various colors of socks in his chest of drawers. The colors of the socks are represented by integers from $1$ to $N$, and there are $A_i\ (\geq 2)$ socks of color $i$.

He is about to choose which socks to wear today by performing the following operation:

• Continue to randomly draw one sock at a time from the chest, with equal probability, until he can make a pair of socks of the same color from those he has already drawn. Once a sock is drawn, it will not be returned to the chest.

Find the expected value, modulo $998244353$, of the number of times he has to draw a sock from the chest.

What does it mean to find the expected value modulo $998244353$? It can be proved that the sought expected value is always rational. Furthermore, the constraints of this problem guarantee that if the expected value is expressed as an irreducible fraction $\frac{y}{x}$, then $x$ is not divisible by $998244353$. Here, there exists a unique integer $z$ between $0$ and $998244352$, inclusive, such that $xz \equiv y \pmod{998244353}$. Find this $z$.

Constraints

• $1\leq N \leq 3\times 10^5$
• $2\leq A_i \leq 3000$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$

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

Output

Print the answer.

Sample Input 1

2
2 2

Sample Output 1

665496238

For example, the operation could be performed as follows:

1. Draw a sock of color $1$ from the chest. There remains one sock of color $1$ and two socks of color $2$ in the chest.
2. Draw a sock of color $2$ from the chest. There remains one sock each of colors $1$ and $2$ in the chest.
3. Draw a sock of color $1$ from the chest. The socks drawn so far are two of color $1$ and one of color $2$, allowing a pair of color $1$ socks to be made, thus ending the operation.

In this example, Takahashi draws a sock from the chest three times.

The expected number of times Takahashi draws a sock from the chest is $3$ with probability $\frac{2}{3}$ and $2$ with probability $\frac{1}{3}$, so the expected value is $3\times \frac{2}{3} + 2\times \frac{1}{3} = \frac{8}{3} \equiv 665496238 \pmod {998244353}$.

Sample Input 2

1
352

Sample Output 2

2

Sample Input 3

6
1796 905 2768 253 2713 1448

Sample Output 3

887165507