由于考虑范围是所有排列，那么对于每个最终巡游出来的 x\ne k 的排列情况都是对称的。即有 \frac{n!-a}{n-1} 种排列满足最后巡游出某个 x\ne k。
因此，最终答案就是：
ak+\sum_{1\le i\le n,i\ne k}\frac{(n!-a)i}{n-1}
用等差数列求和公式化简一下，即：
ak+\frac{(n!-a)(n(n+1)-2k)}{2n-2}
所以问题就是怎么求 a。
什么时候跑 m 次后 x=k？
形象一点，我们发现给一个排列中每个 p_x 建一条 x\rightarrow p_x 的边，其实 x 就在顺着边在图里不停地跑，而这个图长什么样子？当然就是几个环啦！x 就从点 k 出发，在包含 k 的环里一圈一圈绕，共走 m 步。 而最终 x=k 就说明 x 绕回到点 k 了！这说明这个环的长度是 m 的因子，可以整除 m。
所以我们可以用枚举 m 的因子的方式枚举环的长度 d，并算出环长为 d 的时候有多少种可能。换句话说，有多少种排列满足巡游 d 次后 x=k，且前 d-1 次巡游后都满足 x\ne k。
不妨找规律：
$d=2$ 时，即 $p_k\ne k$ 的同时 $p_{p_k}=k$，满足前者就是 $n!-(n-1)!$ 个排列，满足后者又是这些情况的 $\frac{1}{n-1}$（$p_{p_k}$ 在除了已经确定的 $p_k$ 之外的其他数字中选出 $k$ 的概率），综上为 $(n!-(n-1)!)\times\frac{1}{n-1}=(n-1)!$。
$d=3$ 时，就是 $d=2$ 的情况中 $p_{p_k}$ 在除了已经确定的 $p_k$ 之外的其他数字中选出**不是** $k$ 的情况数，再乘上 $p_{p_{p_k}}$ 在除了已经确定的 $p_k,p_{p_k}$ 之外的其他数字中选出 $k$ 的概率，就是 $(n!-(n-1)!)\times\frac{n-2}{n-1}\times\frac{1}{n-2}=(n-1)!$。
类似地，$d=4$ 时情况数为 $(n!-(n-1)!)\times\frac{n-2}{n-1}\times\times\frac{n-3}{n-2}\times\frac{1}{n-3}=(n-1)!$。
以此类推。
发现无论环长是多少，这样的排列数都是 $(n-1)!$。
不严谨的理解：$d=1$ 的时候是 $(n-1)!$，一般来说这个情况数随着 $d$ 增大要么减少要么增加要么不变，而发现 $d$ 取值有 $n$ 种情况，$(n-1)!\times n=n!$ 即全部情况，那么我猜他就是不变。
综上，
$$
a=cnt\times(n-1)!
$$
其中 $cnt$ 为 $m$ 的正整数因子中 $\le n$ 的数量。
再放一遍答案：
$$
ak+\frac{(n!-cnt\times(n-1)!)(n(n+1)-2k)}{2n-2}
$$
所以我们预处理阶乘，按照上述式子算就可以了。
## 参考代码
时间复杂度 $O(V+T\sqrt{n})$，$V$ 为 $n$ 取值上限。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353;
int T, n, m, k, jc[10000010];
signed main() {
jc[0] = 1;
for (int i = 1; i <= 10000000; i++)
jc[i] = jc[i - 1] * i % MOD;
cin >> T;
while (T--) {
cin >> n >> m >> k;
if (m == 0) cout << jc[n] * k % MOD << endl;
else {
int cnt = 0;
for (int i = 1; i * i <= m; i++) {
if (m % i != 0) continue;
if (i <= n) cnt++;
if (i != m / i && m / i <= n) cnt++;
}
int othersum = ((n + 1) * n / 2 % MOD - k + MOD) % MOD;
int ans =
k * jc[n - 1] % MOD * cnt % MOD +
othersum * jc[n - 2] % MOD * (n - cnt) % MOD;
cout << ans % MOD << endl;
}
}
return 0;
}
```
如果你有任何疑问或者觉得讲得不好的地方，欢迎留言！
~~如果没有，点赞。~~