You are given an array $a$ of length $2n$. Consider a partition of array $a$ into two subsequences $p$ and $q$ of length $n$ each (each element of array $a$ should be in exactly one subsequence: either in $p$ or in $q$).

Let's sort $p$ in non-decreasing order, and $q$ in non-increasing order, we can denote the sorted versions by $x$ and $y$, respectively. Then the cost of a partition is defined as $f(p, q) = \sum_{i = 1}^n |x_i - y_i|$.

Find the sum of $f(p, q)$ over all correct partitions of array $a$. Since the answer might be too big, print its remainder modulo $998244353$.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 150\,000$).

The second line contains $2n$ integers $a_1, a_2, \ldots, a_{2n}$ ($1 \leq a_i \leq 10^9$) — elements of array $a$.


-----Output-----

Print one integer — the answer to the problem, modulo $998244353$.


-----Examples-----
Input
1
1 4

Output
6
Input
2
2 1 2 1

Output
12
Input
3
2 2 2 2 2 2

Output
0
Input
5
13 8 35 94 9284 34 54 69 123 846

Output
2588544


-----Note-----

Two partitions of an array are considered different if the sets of indices of elements included in the subsequence $p$ are different.

In the first example, there are two correct partitions of the array $a$:  $p = [1]$, $q = [4]$, then $x = [1]$, $y = [4]$, $f(p, q) = |1 - 4| = 3$;  $p = [4]$, $q = [1]$, then $x = [4]$, $y = [1]$, $f(p, q) = |4 - 1| = 3$. 

In the second example, there are six valid partitions of the array $a$:   $p = [2, 1]$, $q = [2, 1]$ (elements with indices $1$ and $2$ in the original array are selected in the subsequence $p$);  $p = [2, 2]$, $q = [1, 1]$;  $p = [2, 1]$, $q = [1, 2]$ (elements with indices $1$ and $4$ are selected in the subsequence $p$);  $p = [1, 2]$, $q = [2, 1]$;  $p = [1, 1]$, $q = [2, 2]$;  $p = [2, 1]$, $q = [2, 1]$ (elements with indices $3$ and $4$ are selected in the subsequence $p$).

Difficulty: competition

Starter code:

Solutions:

import sys
from sys import stdin

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): 
    return fac[n] * inv[n-r] * inv[r] % mod

mod = 998244353

n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
a.sort()
fac,inv = modfac(2*n+10,mod)

print( (modnCr(2*n,n,mod,fac,inv) * (sum(a[n:]) - sum(a[:n]))) % mod )


n = int(input())
l = sorted(map(int, input().split()))
tot = sum(l[n:]) - sum(l[:n])
MOD = 998244353
fact = [1]
for i in range(1, 2 * n + 1):
    fact.append((fact[-1] * i) % MOD)
tot *= fact[2 * n]
inv = pow(fact[n], MOD-3, MOD)
tot *= inv
print(tot % MOD)

import sys
input = sys.stdin.readline
mod=998244353
n=int(input())
a=list(map(int,input().split()))
a.sort()
val=0
for i in range(n):
    val+=a[-i-1]
    val-=a[i]
facs=[1]
for i in range(2*n):
    facs.append((facs[-1]*(i+1))%mod)
numb=facs[2*n]
numb*=pow(facs[n]**2,mod-2,mod)
numb*=val
numb%=mod
print(numb)

import sys
readline = sys.stdin.readline

MOD = 998244353
def make_fac(limit):
    fac = [1]*limit
    for i in range(2,limit):
        fac[i] = i * fac[i-1]%MOD
    faci = [0]*limit
    faci[-1] = pow(fac[-1], MOD -2, MOD)
    for i in range(limit-2, 0, -1):
        faci[i] = faci[i+1] * (i + 1) % MOD
    return fac, faci
fac, faci = make_fac(341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return fac[a]*faci[b]*faci[a-b]%MOD
N = int(readline())
A = list(map(int, readline().split()))

A.sort()
print((sum(A[N:]) -  sum(A[:N]))%MOD*comb(2*N, N)%MOD)