CF2223B.Zhily and Barknights

Zhily developed a game called Barknights, and she is preparing to release a major update on March $25$. Specifically, she plans to add a Module to each Operator in the game, multiplying their power level by the Module's power.

After the update is released, the famous game streamer Jily will evaluate the Operators' power levels and rank them in a tier list. Whenever an earlier-released Operator is ranked higher than a later-released Operator, it will cause a wave of drama.

Unfortunately, Zhily accidentally knocked over a hot water kettle and broke her computer, which caused all the Modules to be randomly rearranged. Now Zhily wants to know the expected number of waves of drama that will be generated, but since she has to move on to the next problem, she has entrusted this task to you.

You are given two arrays $a$ and $b$ of $n$ positive integers. Let $b'$ be a permutation of array $b$ chosen uniformly at random among all $n!$ possible permutations. Define $ c_i = a_i \cdot b'_i$ for $1\le i \le n$.

Find the expected number of inversions$^{\text{∗}}$ of array $c$.

$^{\text{∗}}$An inversion in array $c$ is a pair of indices $(i, j)$ such that $1 \le i \lt j \le n$ and $c_i \gt c_j$.

芝莉开发了一款名为《 Barknights 》的游戏，并计划于 $3$ 月 $25$ 日发布一次重大更新。具体而言，她打算为游戏中的每位干员（Operator）添加一个模组（Module），该模组会将其战力值乘以模组自身的战力系数。

更新发布后，知名游戏主播吉莉（Jily）将对各位干员的战力值进行评估，并据此制作一份战力排行表（tier list）。每当一名更早实装的干员在排行榜中排在一名更晚实装的干员之前时，便会引发一场“争议风波”（drama）。

不幸的是，芝莉不小心打翻了热水壶，导致电脑损坏，所有模组因此被随机打乱了分配顺序。现在芝莉想知道：此次更新将引发的“争议风波”的期望次数是多少？但由于她必须立刻着手解决下一个问题，因此将这一任务托付给了你。

给你两个长度为 $n$ 的正整数数组 $a$ 和 $b$。令 $b'$ 是数组 $b$ 在全部 $n!$ 种可能排列中均匀随机选取的一个排列。定义 $ c_i = a_i \cdot b'_i$，其中 $1 \le i \le n$。

请计算数组 $c$ 中逆序对（inversion）数量的期望值。

$^{\text{∗}}$ 数组 $c$ 中的一个逆序对是指一对下标 $(i, j)$，满足 $1 \le i \lt j \le n$ 且 $c_i \gt c_j$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2000$) — the length of the arrays $a$ and $b$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the array $a$.

The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^9$) — the array $b$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output the expected number of inversions in $c$ modulo $998\,244\,353$.

Formally, let $M = 998\,244\,353$. It can be shown that the exact answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

对于每个测试用例，输出数组 $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$。换言之，输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

In the first test case, since all elements of $b$ are $1$, any of the $5!$ permutations results in $b' = (1, 1, 1, 1, 1)$. Thus, $c = (1, 14, 5, 1, 4)$ is always constant. The inversions are $(2, 3), (2, 4), (2, 5), (3, 4),$ and $(3, 5)$. The expected number of inversions is $5 \equiv 5 \pmod{998\,244\,353}$.

In the second test case, there are $3! = 6$ equally likely permutations $b'$. The resulting arrays $c$ and their respective inversion counts are shown below:

$b'$

$c = (3b'_1, 2b'_2, 5b'_3)$

Inversion Count

$(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

The expected number of inversions is $\frac{1+0+0+0+2+1}{6} = \frac{4}{6} = \frac{2}{3}$.

Modulo $998\,244\,353$, the answer is $2 \cdot 3^{-1} \equiv 665\,496\,236 \pmod{998\,244\,353}$.

在第一个测试用例中，由于 $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}$。