You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

# Problem
In Homer's school, there are $$$n$$$ students who love clubs.

Initially, there are $$$m$$$ clubs, and each of the $$$n$$$ students is in exactly one club. In other words, there are $$$a_i$$$ students in the $$$i$$$-th club for $$$1 \leq i \leq m$$$ and $$$a_1+a_2+\dots+a_m = n$$$.

The $$$n$$$ students are so unfriendly that every day one of them (chosen uniformly at random from all of the $$$n$$$ students) gets angry. The student who gets angry will do one of the following things.

- With probability $$$\frac 1 2$$$, he leaves his current club, then creates a new club himself and joins it. There is only one student (himself) in the new club he creates.
- With probability $$$\frac 1 2$$$, he does not create new clubs. In this case, he changes his club to a new one (possibly the same club he is in currently) with probability proportional to the number of students in it. Formally, suppose there are $$$k$$$ clubs and there are $$$b_i$$$ students in the $$$i$$$-th club for $$$1 \leq i \leq k$$$ (before the student gets angry). He leaves his current club, and then joins the $$$i$$$-th club with probability $$$\frac {b_i} {n}$$$.

Homer wonders the expected number of days until every student is in the same club for the first time.

We can prove that the answer can be represented as a rational number $$$\frac p q$$$ with $$$\gcd(p, q) = 1$$$. Therefore, you are asked to find the value of $$$pq^{-1} \bmod 998\,244\,353$$$. It can be shown that $$$q \bmod 998\,244\,353 \neq 0$$$ under the given constraints of the problem.

## Input Format
The first line contains an integer $$$m$$$ ($$$1 \leq m \leq 1000$$$) — the number of clubs initially.

The second line contains $$$m$$$ integers $$$a_1, a_2, \dots, a_m$$$ ($$$1 \leq a_i \leq 4 \cdot 10^8$$$) with $$$1 \leq a_1+a_2+\dots+a_m \leq 4 \cdot 10^8$$$, where $$$a_i$$$ denotes the number of students in the $$$i$$$-th club initially.

## Output Format
Print one integer — the expected number of days until every student is in the same club for the first time, modulo $$$998\,244\,353$$$.

## Examples
```input
2
1 1
```
```output
4
```
-----
```input
2
1 2
```
```output
18
```
-----
```input
3
1 1 1
```
```output
21
```
-----
```input
1
400000000
```
```output
0
```
-----
```input
10
1 2 3 4 5 6 7 8 9 10
```
```output
737609878
```

## Note
In the first example, no matter which student gets angry, the two students will become in the same club with probability $$$\frac 1 4$$$. So the expected number of days until every student is in the same club should be $$$4$$$.

In the second example, we note that in the first day:

- The only student in the first club will get angry with probability $$$\frac 1 3$$$. If he gets angry, then he will create a new club and join it with probability $$$\frac 1 2$$$ (In this case, there will be three clubs which have $$$0, 1, 2$$$ students in it, respectively), leave his current club and join the second club with probability $$$\frac 1 2 \cdot \frac 2 3 = \frac 1 3$$$, or stay still with probability $$$\frac 1 2 \cdot \frac 1 3 = \frac 1 6$$$;
- Each of the two students in the second club will get angry with probability $$$\frac 1 3$$$. If one of them gets angry, then he will create a new club and join it with probability $$$\frac 1 2$$$, leave his current club and join the second club with probability $$$\frac 1 2 \cdot \frac 1 3 = \frac 1 6$$$, or stay still with probability $$$\frac 1 2 \cdot \frac 2 3 = \frac 1 3$$$.

In the fourth example, there is only one club initially. That is, every student has already been in the same club. So the answer is $$$0$$$.

Now solve the problem and return the code.