Жили разработала игру под названием Barknights и готовится выпустить крупное обновление $$$25$$$ марта. В частности, она планирует добавить модуль для каждого оператора в игре, умножная их уровень мощности на мощности модуля.
После выхода обновления известный стример Джили оценит силу операторов и составит их рейтинг. Каждый раз, когда оператор, выпущенный раньше, окажется выше в рейтинге, чем оператор, выпущенный позже, это вызовет бурную реакцию.
К сожалению, Жили случайно опрокинула чайник с горячей водой и сломала свой компьютер, в результате чего все модули перемешались в случайном порядке. Теперь Жили хочет узнать, сколько волн реакций, по ее прогнозам, возникнет, но поскольку ей нужно переходить к следующей задаче, она поручила эту работу вам.
Даны два массива $$$a$$$ и $$$b$$$, содержащие по $$$n$$$ целых положительных чисел. Пусть $$$b'$$$ — перестановка массива $$$b$$$, выбранная равномерно случайным образом из всех $$$n!$$$ возможных перестановок. Определим $$$ c_i = a_i \cdot b'_i$$$ для $$$1\le i \le n$$$.
Найдите ожидаемое число инверсий$$$^{\text{∗}}$$$ массива $$$c$$$.
$$$^{\text{∗}}$$$Инверсия в массиве $$$c$$$ — это пара индексов $$$(i, j)$$$, такая что $$$1 \le i \lt j \le n$$$ и $$$c_i \gt c_j$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$1 \le n \le 2000$$$) — длина массивов $$$a$$$ и $$$b$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — массив $$$a$$$.
Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — массив $$$b$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.
Для каждого набора входных данных выведите ожидаемое количество инверсий в строке $$$c$$$ по модулю $$$998\,244\,353$$$.
Формально, пусть $$$M = 998\,244\,353$$$. Можно показать, что точный ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x \lt M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.
351 14 5 1 41 1 1 1 133 2 53 2 51010 72 65 43 73 23 78 13 49 9931 90 45 19 44 18 59 31 48 29
5665496236820778710
В первом наборе входных данных, поскольку все элементы $$$b$$$ равны $$$1$$$, любая из $$$5!$$$ перестановок приводит к $$$b' = (1, 1, 1, 1, 1)$$$. Таким образом, $$$c = (1, 14, 5, 1, 4)$$$ в любой ситуации. Инверсии: $$$(2, 3), (2, 4), (2, 5), (3, 4)$$$ и $$$(3, 5)$$$. Ожидаемое количество инверсий равно $$$5 \equiv 5 \pmod{998\,244\,353}$$$.
Во втором наборе входных данных существует $$$3! = 6$$$ равновероятных перестановок $$$b'$$$. Результирующие массивы $$$c$$$ и соответствующее количество инверсий приведены ниже:
| $$$b'$$$ | $$$c = (3b'_1, 2b'_2, 5b'_3)$$$ | Количество инверсий |
| $$$(3, 2, 5)$$$ | $$$(9, 4, 25)$$$ | 1 |
| $$$(3, 5, 2)$$$ | $$$(9, 10, 10)$$$ | 0 |
| $$$(2, 3, 5)$$$ | $$$(6, 6, 25)$$$ | 0 |
| $$$(2, 5, 3)$$$ | $$$(6, 10, 15)$$$ | 0 |
| $$$(5, 3, 2)$$$ | $$$(15, 6, 10)$$$ | 2 |
| $$$(5, 2, 3)$$$ | $$$(15, 4, 15)$$$ | 1 |
Ожидаемое количество инверсий равно $$$\frac{1+0+0+0+2+1}{6} = \frac{4}{6} = \frac{2}{3}$$$.
По модулю $$$998\,244\,353$$$ ответ равен $$$2 \cdot 3^{-1} \equiv 665\,496\,236 \pmod{998\,244\,353}$$$.
