Problem Description

You are given an array \(a\) of length \(2n\). Consider a partition of the array into two subsequences \(p\) and \(q\), each of length \(n\) (each element of \(a\) belongs to exactly one of \(p\) or \(q\)).

Sort \(p\) in non-decreasing order to obtain \(x\), and sort \(q\) in non-increasing order to obtain \(y\). 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 \(a\). Since the answer may be large, output it modulo \(998244353\).

Input

The first line contains a single integer \(n\) (\(1 \le n \le 150\,000\)).
The second line contains \(2n\) integers \(a_1, a_2, \dots, a_{2n}\) (\(1 \le a_i \le 10^9\)).

Output

Print one integer — the answer modulo \(998244353\).

Examples

input #1

1
1 4

output #1

6

input #2

2
2 1 2 1

output #2

12

input #3

3
2 2 2 2 2 2

output #3

0

input #4

5
13 8 35 94 9284 34 54 69 123 846

output #4

2588544

Note

Two partitions are considered different if the sets of indices of the elements chosen for \(p\) are different.

Solution

Let the original array be sorted in non‑decreasing order: \(b_1 \le b_2 \le \dots \le b_{2n}\). A key combinatorial observation is that for any valid partition, the multiset of \(y\) (the sorted \(q\) in non‑increasing order) is always the \(n\) largest elements, and the multiset of \(x\) (the sorted \(p\) in non‑decreasing order) is the \(n\) smallest elements.

Define \[ S_{\text{small}} = \sum_{i=1}^{n} b_i, \qquad S_{\text{large}} = \sum_{i=n+1}^{2n} b_i. \] Then the total sum of costs over all partitions can be expressed as \[ \text{Answer} = 2 \cdot \binom{2n-1}{n-1} \cdot (S_{\text{large}} - S_{\text{small}}) \bmod 998244353. \] An equivalent way to compute it is to sum over the number of indices \(i\) where \(y_i \ge x_i\). This leads to the identity \[ \sum_{i=1}^{n} \frac{i}{n} \binom{n}{i}^2 = \binom{2n-1}{n-1}, \] so the answer can be computed by iterating over \(i\) and accumulating contributions. The implementation below uses this approach.

Implementation

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const long long MOD = 998244353;

long long mod_pow(long long a, long long e) {
    long long res = 1;
    while (e) {
        if (e & 1) res = res * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    int len = 2 * n;
    vector<long long> arr(len);
    for (int i = 0; i < len; ++i) cin >> arr[i];
    sort(arr.begin(), arr.end());
    
    // factorials and inverses up to n
    vector<long long> fact(n + 1), inv_fact(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % MOD;
    inv_fact[n] = mod_pow(fact[n], MOD - 2);
    for (int i = n; i >= 1; --i) inv_fact[i - 1] = inv_fact[i] * i % MOD;
    
    // combinations C(n, k)
    auto C = [&](int n, int k) -> long long {
        if (k < 0 || k > n) return 0;
        return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
    };
    
    long long sum_small = 0, sum_large = 0;
    for (int i = 0; i < n; ++i) sum_small = (sum_small + arr[i]) % MOD;
    for (int i = n; i < len; ++i) sum_large = (sum_large + arr[i]) % MOD;
    
    long long diff = (sum_large - sum_small + MOD) % MOD;
    long long inv_n = mod_pow(n, MOD - 2);
    
    long long coeff_sum = 0;
    for (int i = 1; i <= n; ++i) {
        long long comb = C(n, i);
        long long term = comb * comb % MOD * i % MOD;
        coeff_sum = (coeff_sum + term) % MOD;
    }
    long long ans = 2LL * coeff_sum % MOD * inv_n % MOD * diff % MOD;
    cout << ans << '\n';
    
    return 0;
}