"Hunter Kill" is a fan-made version of the popular game "Werewolf." Its rules are as follows:

Initially, there are $n$ hunters, and the $i$-th hunter has a hatred value $w_i$. Each hunter has only one fixed ability: upon death, they must fire a shot, and the person hit will also die.

However, there is a specific rule for choosing who to shoot. Suppose the currently living hunters are $[i_1, \ldots, i_m]$. The probability of shooting hunter $i_k$ is $\frac{w_{i_k}}{\sum_{j = 1}^{m} w_{i_j}}$.

The first shot is fired by you, and the target selection method is the same as that of the hunters (i.e., there is a $\frac{w_i}{\sum_{j=1}^{n}w_j}$ probability of hitting the $i$-th hunter). Due to the chain reaction caused by the shooting, all hunters will eventually die. Now, hunter $1$ wants to know the probability that they are the last one to die.

The answer should be taken modulo $998244353$.

Input

The first line contains a positive integer $n$.

The second line contains $n$ positive integers, where the $i$-th integer represents $w_i$.

Output

Output the answer.

Examples

Input 1

3
1 1 2

Output 1

915057324

Note 1

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

Subtasks

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

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

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

An additional $10\%$ of the data satisfies $1\leq w_i\leq 2$ and $w_1=1$.

An additional $10\%$ of the data satisfies $1\leq w_i\leq 2$ and $w_1=2$.

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