本题没有可用的提交语言。

题目描述

在某游戏中，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$ 行，每行一个整数，表示答案。

1
1 2 1

1

提示

在样例中，$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 范围内。