Problem Statement

There are $N$ cards numbered $1$ to $N$. Card $i$ has an integer $A_i$ written on it. Here, $N$ is even.

Snuke and Robot will play a game, which will go as follows.

• The game master announces a permutation $(p_1,p_2,\cdots,p_N)$ of $(1,2,\cdots,N)$, to both Snuke and Robot.
• Then, Snuke and Robot alternately take turns, with Snuke going first. Each turn goes as follows.
• Snuke's turn: choose a remaining card of his choice and eat it.
  • Robot's turn: choose Card $i$ with the largest $p_i$ and burn it.
• The game ends when there is no more card.

The final score of the game is the sum of integers written on the cards eaten by Snuke. Snuke will play optimally to maximize the score.

There are $N!$ permutations $p$ of $(1,2,\cdots,N)$. Find the sum, modulo $998244353$, of the final scores for all of these permutations.

Constraints

• $1 \leq N \leq 10^6$
• $N$ is even.
• $1 \leq A_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.