P11256 [GDKOI2023 Junior] Permutation

Moon has recently been playing a card game called Shadowverse. During the game, Moon thought of a shuffling problem. Suppose there are $n$ cards in the deck. The label of the $i$-th card is $i$. We define a shuffling method as a permutation $X=\{x_1, x_2, ..., x_n\}$, meaning that the card in position $i$ in the deck is moved to position $x_i$. Now suppose Moon shuffles the deck $k$ times using the method $X$. Let the final permutation be $Y=\{y_1, y_2, ..., y_n\}$, where $y_i$ denotes the label of the $i$-th card after shuffling. Moon wants you to compute how many valid shuffling methods $X$ satisfy that after shuffling $k$ times, the result becomes permutation $Y$. Since the answer may be very large, you only need to output the answer modulo $998244353$. Formally, for a permutation $P=\{p_1, p_2, ..., p_n\}$ and a permutation $Q=\{q_1, q_2, ..., q_n\}$, define their product as: $$ P \times Q = \{q_{p1} , q_{p2} , ..., q_{pn} \}$$ The $k$-th power $X^k$ of permutation $X$ is the product of $k$ copies of $X$. Now given a permutation $Y$ and a positive integer $k$, compute the number of permutations $X$ that satisfy the equation $X^k = Y$, modulo $998244353$.

The first line contains an integer $T$, denoting the number of testdata cases. Each test case consists of two lines. The first line contains two positive integers $n, k$, representing the length of permutations $X$ and $Y$, and that the deck is shuffled $k$ times. The second line contains $n$ distinct positive integers $\{y_1, y_2, ..., y_n\}$ from $1$ to $n$, representing permutation $Y$.

Output $T$ lines. Each line contains one integer, representing the number of valid shuffling methods, modulo $998244353$.

### Sample Explanation In the sample, $X = [3,4,2,1,5]$ or $[4,3,1,2,5]$. There are $2$ valid permutations in total. ### Constraints For all testdata, $1 \le n \le 3000$, $1 \le k \le 10^6$, $1 \le T \le 10$. For $20\%$ of the testdata, $1 \le n, k \le 8$. For another $10\%$ of the testdata, only $1 \le n \le 8$ is guaranteed. For another $30\%$ of the testdata, only $1 \le n \le 50$ is guaranteed. Translated by ChatGPT 5