Aoba-san 提出了以下问题。
最大括号得分
给定一个长度为 $2N$ 的整数序列 $A = (A_1, A_2, \dots, A_{2N})$。
对于一个长度为 $2N$ 的合法括号序列 $s$，其得分定义如下：
* 所有满足 $s_i$ 为 ( 的下标 $i$ 对应的 $A_i$ 之和。
求在所有长度为 $2N$ 的合法括号序列中，得分的最大值。
Hirose-san 认为这太简单了，于是提出了以下问题。
洗牌与最大括号得分
给定一个长度为 $2N$ 的整数序列 $A = (A_1, A_2, \dots, A_{2N})$。 将 $A$ 均匀随机打乱后，计算“最大括号得分”问题的答案的期望值，对 $998244353$ 取模。
请解决“洗牌与最大括号得分”问题。
合法括号序列的定义
如果一个字符串满足以下条件之一，则称其为合法括号序列：
它是空字符串。
它是 (、$s$、) 的拼接，其中 $s$ 是某个合法括号序列。
* 它是 $s$ 和 $t$ 的拼接，其中 $s$ 和 $t$ 是某些合法括号序列。
期望值对 998244353 取模的定义
可以证明所求的期望值总是一个有理数。此外，在本问题的约束条件下，保证当所求期望值表示为既约分数 $\frac{y}{x}$ 时，$x$ 不能被 $998244353$ 整除。在这种情况下，存在唯一的整数 $0 \le z < 998244353$ 满足 $y \equiv xz \pmod{998244353}$，输出该 $z$ 即可。
输入格式
输入通过标准输入给出，格式如下：
$N$ $A_1 \ A_2 \ \dots \ A_{2N}$
- $1 \le N \le 10^5$
- $1 \le A_i \le 10^9$
- 所有输入值均为整数。
输出格式
在一行中输出答案。
样例
样例 1
输入
1 1 2
输出
499122178
样例 2
输入
2 1 2 3 4
输出
831870300
样例 3
输入
4 31415 92653 58979 32384 62643 38327 95028 84197
输出
420993474
说明
对于第一个样例：
当 $A = (1, 2)$ 时，“最大括号得分”问题的答案为 $1$。
当 $s$ 为 () 时，得分为 $1$。
当 $A = (2, 1)$ 时，“最大括号得分”问题的答案为 $2$。
当 $s$ 为 () 时，得分为 $2$。
期望值为 $\frac{1}{2}(1 + 2) = \frac{3}{2}$。
对于第二个样例：
例如，当 $A = (1, 2, 3, 4)$ 时，“最大括号得分”问题的答案为 $4$。
当 $s$ 为 ()() 时，得分为 $1 + 3 = 4$。
当 $s$ 为 (()) 时，得分为 $1 + 2 = 3$。
类似地，当 $A = (4, 3, 2, 1)$ 时，“最大括号得分”问题的答案为 $7$。
当 $s$ 为 ()() 时，得分为 $4 + 2 = 6$。
当 $s$ 为 (()) 时，得分为 $4 + 3 = 7$。
期望值为 $\frac{35}{6}$。