Permutation Shuffling and k-th Roots Problem

Moon is playing a card game called Shadowverse. In the course of the game he encountered an interesting shuffling problem. Initially there is a deck of n cards numbered 1 through n in that order. A shuffling method is defined by a permutation X = {x₁, x₂, …, xₙ}, meaning that after shuffling, the card originally in position i will move to position xᵢ.

If Moon shuffles the deck k times using the same method X, the final configuration of the deck becomes the permutation Y = {y₁, y₂, …, yₙ} where y_i is the number on the card in position i after all shuffles. In other words, we define the product of two permutations P = {p₁, p₂, …, pₙ} and Q = {q₁, q₂, …, qₙ} as

$$ P \times Q = \{q_{p_1},q_{p_2},\dots,q_{p_n}\} $$

and the k-th power of a permutation X is defined as

$$ X^k = \underbrace{X \times X \times \cdots \times X}_{k \text{ times}}.$$

Your task is to count the number of valid shuffling methods (i.e. permutations X) that satisfy

$$ X^k = Y. $$

Since the answer can be very large, output it modulo 998244353.

Note: A permutation is an arrangement of numbers 1 to n. The problem of finding a k-th root of a permutation is solved by analyzing the cycle structure of Y. Suppose a cycle in X has length L. Then when raised to the power k, it breaks up into \(\gcd(L, k)\) cycles of length \(\frac{L}{\gcd(L,k)}\). In order for X^k to equal Y, the cycles of Y must be partitioned into groups corresponding to the cycles in X. This problem requires you to count the number of ways this can be done over all cycle lengths.

inputFormat

The first line contains two integers n and k (1 ≤ n, k ≤ 10⁵), indicating the number of cards and the number of times the deck is shuffled.

The second line contains n distinct integers y₁, y₂, …, yₙ which form a permutation of {1, 2, …, n} representing the final deck configuration Y.

outputFormat

Output a single integer – the number of valid shuffling methods (permutations X) such that X^k = Y, taken modulo 998244353.

sample

3 1
1 2 3

1