Description

Hunter Kill is a folk version of the once-popular game “Werewolf”. The rules are as follows.

At the beginning, there are $n$ hunters. The $i$-th hunter has a hatred value $w_i$. Each hunter has only one fixed skill: after dying, they must fire one shot, and the person who is shot will also die.

However, choosing whom to shoot is also important. Suppose the hunters still alive are $[i_1\ldots i_m]$. Then the probability of shooting hunter $i_k$ is $\frac{w_{i_k}}{\sum_{j = 1}^{m} w_{i_j}}$.

At the beginning, the first shot is fired by you, and the target is chosen in the same way as the hunters (that is, hunter $i$ is hit with probability $\frac{w_i}{\sum_{j=1}^{n}w_j}$). Due to the chain reaction caused by shooting, all hunters will eventually die. Now hunter $1$ wants to know the probability that they are the last one to die.

Output the answer modulo $998244353$.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers. The $i$-th positive integer denotes $w_i$.

Output Format

Output the answer.

3
1 1 2

915057324

Hint

Sample Explanation

The answer is $\frac{2}{4}\times \frac{1}{2}+\frac{1}{4}\times \frac{2}{3}=\frac{10}{24}$.

For $10\%$ of the testdata, $1\leq n\leq 10$.

For $30\%$ of the testdata, $1\leq n\leq 20$.

For $50\%$ of the testdata, $1\leq \sum\limits_{i=1}^{n}w_i\leq 5000$.

For another $10\%$ of the testdata, $1\leq w_i\leq 2$, and $w_1=1$.

For another $10\%$ of the testdata, $1\leq w_i\leq 2$, and $w_1=2$.

For $100\%$ of the testdata, $w_i>0$, and $1\leq \sum\limits_{i=1}^{n}w_i \leq 100000$.

Translated by ChatGPT 5