给定 $n$ 个数的序列 $a_{1\cdots n}$，你需要求出每一个排列 $p_{1\cdots n}$ 的权值之和模 $998244353$ 的值。

对于一个排列 $p_{1\cdots n}$，它的权值定义如下：

• 两个人 W 和 L 轮流玩游戏，W 先手。
• 在 W 的回合，她可以取走序列中的一个数字。
• 在 L 的回合，他必须取走当前剩下的所有数字中，$p_i$ 最大的 $a_i$。
• 序列中没有数的时候游戏结束。

权值为 W 通过最优策略获得的最大数字之和。

$1\le n\le 10^6$，$1\le a_i\le 10^9$，$n$ 为偶数。

输入格式

第一行输入一个正整数 $n$。

第二行输入 $n$ 个正整数 $a_{1},a_2\cdots a_n$

输出格式

输出一行答案。

样例 #1

样例输入 #1

2
1 2

样例输出 #1

4

样例 #2

样例输入 #2

4
1 100 10000 1000000

样例输出 #2

24200400

样例 #3

样例输入 #3

10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117

样例输出 #3

710984634