P12181 DerrickLo's Buildings (UBC002D)

In a game, DerrickLo needs to complete a task of managing a bunch of buildings. These buildings are placed on position $1$ to $M$. Their heights are $1$ to $M$, too. Initially, the building with height $i$ is placed on position $i$, for each $i$ from $1$ to $M$. There are also $M$ challenges, the $i$-th challenge contains a height factor $l = i$ and a target length $N$. The **score** of this challenge is the number of $j$ from $1$ to $N$ such that the building with height $j$ is placed on position $(j \times l)$ after rearranging the positions of the buildings. **Note that the target lengths of each challenge are the same, but the height factors are distinct.** To rearrange the buildings, DerrickLo needs to give a *shift* permutation $v$. Whenever he *shifts*, he moves the building on position $i$ to position $v(i)$ for each $i$ from $1$ to $M$ **simultaneously**. Since DerrickLo is not interested in whether he achieved the maximum score, the shift permutation $v$ is chosen **uniformly** from all permutations of $\{1, 2, \dots, M\}$. However, he is curious that for each challenge $i$, what is the expected score if he shifts $1, 2, \dots, V$ times separately. Because the number of challenges and shifts are too big, DerrickLo wants you to calculate the sum of the expected scores modulo $998244353$, that is, $$ \left(\sum_{i=1}^M\sum_{k=1}^VE\left(\sum_{j=1}^N[v_k(j) = i \times j]\right)\right) \bmod 998244353 $$ where $v_k(j)$ is the position of building with height $j$ after shifting $k$ times based on the shift permutation $v$.

**This problem has multiple testcases.** The first line contains an integer $T$, the number of testcases. The following $T$ lines, each contains three integers $N, M, V$, which discribes a testcase. **Note that the input data may NOT fit into a 32-bit integer.**

$T$ lines, each represents an answer to a testcase in given order.

In the sample, $v$ is either $\{1, 2\}$ or $\{2, 1\}$. You need to calculate: $$ \sum_{i=1}^2E([v(1)=i]) $$ When $i = 1$, $E([v(1)=1]) = \frac{1}{2}$. When $i=2$, $E([v(1) = 2]) = \frac{1}{2}$. Thus, the sum is $\frac{1 + 1}{2} = 1$. --- For all testcases: - $1 \le T \le 5$. - $1 \le N \le M \le 10^{12}$. - $2 \le (M \bmod 998244353)$. - $1 \le V \le 10^{12}$. **Note that the input data may NOT fit into a 32-bit integer.**