Expected Maximum Prefix Sum Over Permutations

Little C is a competitive programming enthusiast. One day, he encountered a very difficult problem: to find the maximum subarray sum of a sequence. However, Little C doesn't know how to solve that problem. Instead, he decided to randomly shuffle the sequence and take the maximum prefix sum of the shuffled sequence as his answer.

The maximum prefix sum is defined as follows: given a sequence a₁, a₂, ..., a_n, its prefix sums are S_i = \(\sum_{j=1}^{i} a_j\) for \(1 \le i \le n\), and the maximum prefix sum is \(\max_{1 \le i \le n} S_i\).

Little C is fully aware that his algorithm is not correct for the original problem, so he does not care about the accuracy. Instead, he is only interested in the expected value of the answer he obtains, i.e. the expected maximum prefix sum over all possible random permutations of the sequence. Since the answer might be very complicated, you only need to output the value of (expected answer \(\times n!\)) modulo \(998244353\). Clearly, this result is an integer.

Input Format: The input consists of an integer \(n\) followed by \(n\) integers representing the sequence.

Output Format: Output a single integer: the value of (\(n!\) multiplied by the expected maximum prefix sum) modulo \(998244353\).

inputFormat

The first line contains an integer \(n\) denoting the number of elements in the sequence. The second line contains \(n\) space‐separated integers \(a_1, a_2, \dots, a_n\).

outputFormat

Output a single integer, which is the expected maximum prefix sum over all permutations of the sequence multiplied by \(n!\), modulo \(998244353\).

sample

1
5

5