Вам задан массив \(a\) длины \(2n\). Рассмотрим разбиение массива \(a\) на две подпоследовательности \(p\) и \(q\) длины \(n\) (каждый элемент массива \(a\) должен попасть ровно в одну подпоследовательность: в \(p\) или в \(q\)).
Отсортируем \(p\) по неубыванию, а \(q\) — по невозрастанию, и получим последовательности \(x\) и \(y\), соответственно. Тогда назовём стоимостью разбиения \(f(p, q) = \sum_{i = 1}^n |x_i - y_i|\).
Вам необходимо найти сумму \(f(p, q)\) по всем корректным разбиениям массива \(a\). Так как это число может быть слишком большим, требуется посчитать остаток от деления его на \(998244353\).
Выходные данные
Выведите одно целое число — ответ на задачу по модулю \(998244353\).
Примечание
Два разбиения массива считаются различными, если отличаются наборы индексов элементов, входящих в подпоследовательность \(p\).
В первом примере существует два корректных разбиения массива \(a\):
- \(p = [1]\), \(q = [4]\), тогда \(x = [1]\), \(y = [4]\), \(f(p, q) = |1 - 4| = 3\)
- \(p = [4]\), \(q = [1]\), тогда \(x = [4]\), \(y = [1]\), \(f(p, q) = |4 - 1| = 3\).
Во втором примере существует шесть корректных разбиений массива \(a\):
- \(p = [2, 1]\), \(q = [2, 1]\) (в подпоследовательность \(p\) выбраны элементы с индексами \(1\) и \(2\) исходного массива);
- \(p = [2, 2]\), \(q = [1, 1]\);
- \(p = [2, 1]\), \(q = [1, 2]\) (в подпоследовательность \(p\) выбраны элементы с индексами \(1\) и \(4\) исходного массива);
- \(p = [1, 2]\), \(q = [2, 1]\);
- \(p = [1, 1]\), \(q = [2, 2]\);
- \(p = [2, 1]\), \(q = [2, 1]\) (в подпоследовательность \(p\) выбраны элементы с индексами \(3\) и \(4\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
1 4
|
6
|
|
2
|
2
2 1 2 1
|
12
|
|
3
|
3
2 2 2 2 2 2
|
0
|
|
4
|
5
13 8 35 94 9284 34 54 69 123 846
|
2588544
|