Вам даны перестановка \(p_0, p_1, \ldots, p_{n-1}\) нечётных чисел от \(1\) до \(2n-1\) и перестановка \(q_0, q_1, \ldots, q_{k-1}\) целых чисел от \(0\) до \(k-1\).
Определим массив \(a_0, a_1, \ldots, a_{nk-1}\) длины \(nk\) в соответствии со следующим правилом:
\(a_{i \cdot k+j}=p_i \cdot 2^{q_j}\) для всех \(0 \le i < n\) и всех \(0 \le j < k\) Например, если \(p = [3, 5, 1]\) и \(q = [0, 1]\), то \(a = [3, 6, 5, 10, 1, 2]\).
Обратите внимание, что все массивы в условии нумеруются с нуля. Также обратите внимание, что каждый элемент массива \(a\) определён однозначно.
Найдите количество инверсий в массиве \(a\). Так как ответ может быть очень большим, выведите его по модулю \(998\,244\,353\).
Инверсией в массиве \(a\) называется пара \((i, j)\) (\(0 \le i < j < nk\)), такая что \(a_i > a_j\).
Выходные данные
Для каждого набора входных данных выведите одно число — количество инверсий в массиве \(a\) по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных массив \(a\) равен \([3, 6, 5, 10, 1, 2]\). В нём есть \(9\) инверсий: \((0, 4)\), \((0, 5)\), \((1, 2)\), \((1, 4)\), \((1, 5)\), \((2, 4)\), \((2, 5)\), \((3, 4)\), \((3, 5)\). Обратите внимание, что здесь перечислены пары \((i, j)\), такие что \(i < j\) и \(a_i > a_j\).
Во втором наборе входных данных массив \(a\) равен \([8, 4, 1, 2, 24, 12, 3, 6, 40, 20, 5, 10]\). В нём \(25\) инверсий.
В третьем наборе входных данных массив \(a\) равен \([1, 2, 4, 8, 16]\). В нём нет инверсий.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 2
3 5 1
0 1
3 4
1 3 5
3 2 0 1
1 5
1
0 1 2 3 4
8 3
5 1 7 11 15 3 9 13
2 0 1
|
9
25
0
104
|