Problem Description

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:

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$.

Input Format

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 Format

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

1
5 6
2 1 4 3 5

2

见/example/permutation/下的
permutation1.in

见/example/permutation/下的
permutation1.out

Hint

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