103526: [Atcoder]ABC352 G - Socks 3

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.

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

问题描述

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

他打算通过以下操作来选择今天要穿的袜子：

• 以相等的概率继续从抽屉中随机抽出一只袜子，直到他能从已经抽出的袜子中组成一对同色的袜子。一旦抽出一只袜子，它就不会再放回抽屉。

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

约束条件

• $1\leq N \leq 3\times 10^5$
• $2\leq A_i \leq 3000$
• 所有输入值都是整数。

输入

输入通过标准输入给出以下格式：

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

输出

打印答案。

样例输入1

2
2 2

样例输出1

665496238

例如，操作可以如下进行：

1. 从抽屉中抽出一只颜色为1的袜子。抽屉里剩下一只颜色为1的袜子和两只颜色为2的袜子。
2. 从抽屉中抽出一只颜色为2的袜子。抽屉里剩下一只颜色为1的袜子和一只颜色为2的袜子。
3. 从抽屉中抽出一只颜色为1的袜子。迄今为止抽出的袜子是两只颜色为1的和一只颜色为2的，可以组成一对颜色为1的袜子，操作结束。

在这个例子中，高桥从抽屉里抽出袜子三次。

高桥抽袜子的次数的期望数是3次的概率为$\frac{2}{3}$，2次的概率为$\frac{1}{3}$，所以期望值是$3\times \frac{2}{3} + 2\times \frac{1}{3} = \frac{8}{3} \equiv 665496238 \pmod {998244353}$。

样例输入2

1
352

样例输出2

2

样例输入3

6
1796 905 2768 253 2713 1448

样例输出3

887165507