P12181 DerrickLo's Buildings (UBC002D)

在某游戏中，DerrickLo 的任务是操作一堆建筑。这些建筑被摆放在了编号为 $1$ 到 $M$ 的空位上，它们的高度也分别为 $1$ 到 $M$。一开始，对于所有 $i = 1, 2, \dots, M$，高度为 $i$ 的建筑被摆在了 $i$ 号位置上。 在这个游戏中，有 $M$ 个挑战。具体地，第 $i$ 个挑战都会指定一个高度因数 $l = i$ 和目标长度 $N$，这个挑战的**得分**为在重新摆放建筑后，对于所有 $j = 1, 2, \dots N$，满足高度为 $j$ 的建筑被摆在了 $j \times l$ 号位置的数量。**注意：所有挑战的目标长度都是相同的，但高度因数是互不相同的。** 为了重新摆放这些建筑，DerrickLo 需要指定一个调换排列 $v$，每执行一次调换，就会**同时**将位置 $i$ 上的建筑移到 $v(i)$ 处。 由于 DerrickLo 并不是很看重得分是否最高，因此他指定的排列 $v$ 将是从所有 $1$ 到 $M$ 的排列中**等概率**选取的一个。不过，他还是很好奇，对于每一个挑战 $i$，在他分别调换 $1, 2, \dots, V$ 次时，他的期望得分是多少。 由于挑战的个数以及调换的次数实在太多，DerrickLo 希望你告诉所有这些得分之和模 $998244353$ 之后的结果。即： $$ \left(\sum_{i=1}^M\sum_{k=1}^VE\left(\sum_{j=1}^N[v_k(j) = i \times j]\right)\right)\bmod 998244353 $$ 其中 $v_k(j)$ 表示根据排列 $v$ 调换了 $k$ 次之后，高度为 $j$ 的建筑所在的位置编号。

**本题有多组测试数据。** 第一行，一个正整数 $T$，表示测试数据的个数。 接下来 $T$ 行，每行三个整数 $N, M, V$，描述一个测试数据。 **注意：输入数据不一定在 `int` 范围内。**

共 $T$ 行，每行一个整数，表示答案。

在样例中，$v$ 只有 $\{1, 2\}$ 与 $\{2, 1\}$ 两种取值。你需要计算： $$ \sum_{i=1}^2E([v(1) = i]) $$ 当 $i=1$ 时，$E([v(1) = 1]) = \frac 1 2$；当 $i=2$ 时，$E([v(1) = 2]) = \frac 1 2$。因此，求和之后是 $\frac{1 + 1}{2} = 1$。 --- 对于所有测试数据： - $1 \le T \le 5$。 - $1 \le N \le M \le 10^{12}$。 - $2 \le (M \bmod 998244353)$。 - $1 \le V \le 10^{12}$。 **注意：输入数据不一定在 `int` 范围内。**