Xiao C is an enthusiast of competitive programming. One day, Xiao C encountered a very difficult problem: finding the maximum subarray sum of a sequence.

However, Xiao C does not know how to solve this problem, so he decided to randomly shuffle the sequence and take the maximum prefix sum of the sequence as the answer.

Xiao C is a person with great self-awareness; he knows his algorithm is completely incorrect, so he does not care about the accuracy. He only cares about the expected value of the solution obtained. Now, please help him solve this problem. Since the answer might be very complex, you only need to output the value of the answer multiplied by $n!$ modulo $998244353$. It is clear that this is an integer.

Note: The definition of the maximum prefix sum is the maximum value of $\sum_{j=1}^{i}a_j$ for all $i \in [1,n]$.

Input

The first line contains a positive integer $n$, representing the length of the sequence.

The second line contains $n$ numbers, representing the original sequence $a[1..n]$, where the $i$-th number represents $a[i]$.

Output

Output a non-negative integer representing the answer.

Examples

Input 1

2
-1 2

Output 1

3

Subtasks

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

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

Another $10\%$ of the data satisfies the condition that there is at most one negative number in $a$.

Another $10\%$ of the data satisfies $|a[i]|\leq 2$.

For $100\%$ of the data, $1\leq n\leq 20$ and $\sum_{i=1}^{n}|a[i]|\leq 10^9$.