P11256 [GDKOI2023 普及组] 置换

Moon 最近在玩一款名为 Shadowverse 的卡牌游戏，在非常有趣的游戏过程中，Moon 想到这样一个关于洗牌的问题。假设当前牌堆中有 $n$ 张牌，第 $i$ 张牌的标号为 $i$，我们定义一种洗牌方式是一个排列 $X=\{x_1, x_2, ..., x_n\}$, 也就是把牌堆中第 $i$ 张位置的牌变成第 $x_i$ 张。那么假设现在 Moon 按照 $X$ 的洗牌方式洗了 $k$ 次牌，不妨设最终得到了一个排列 $Y =\{y_1, y_2, ..., y_n\}$，$y_i$ 表示洗完牌后第 $i$ 张牌的标号。Moon 希望你可以帮助他算出有多少合法的洗牌方式 $X$，满足洗了 $K$ 次后变成排列 $Y$ ，由于答案可能很大，所以你只需要输出对 $998244353$ 取模的答案即可。 形式化而言，考虑对于排列 $P=\{p_1, p_2, ..., p_n\}$ 和排列 $Q=\{q_1, q_2, ..., q_n\}$, 定义这两个排列的乘积: $$ P \times Q = \{q_{p1} , q_{p2} , ..., q_{pn} \}$$ 而排列 $X$ 的 $k$ 次幂 $X^k$ 为 $k$ 个排列 $X$ 的乘积，现在考虑给定排列 $Y$ 和正整数 $k$, 求满足方程 $X^k = Y$ 的排列 $X$ 的数量，对 $998244353$ 取模。

无

无

### 样例解释 样例中，$X=[3,4,2,1,5]$ 或者 $[4,3,1,2,5]$, 共两个合法排列。 ### 数据范围 对于所有的数据，有 $1 \le n \le 3000, 1 \le k \le 10^6, 1 \le T \le 10$； 对于 $20\%$ 的数据，有 $1 \le n, k \le 8$； 对于另外 $10\%$ 的数据，仅保证 $1 \le n \le 8$； 对于另外 $30\%$ 的数据，仅保证 $1 \le n \le 50$。