Commutative Square Roots

You are given positive integers $N$, $K$, and a permutation $P$ of $(1,2,\ldots,N)$.

Compute the number of ordered $K$-tuples of permutations $(A_1,A_2,\ldots,A_K)$ of $(1,2,\ldots,N)$ satisfying all of the following conditions, modulo $1\,000\,000\,007$.

• For every $1 \le i \le K$, $A_i \circ A_i = P$.
• For every $1 \le i,j \le K$, $A_i \circ A_j = A_j \circ A_i$.

Composition of permutations is defined as function composition. That is, for two permutations $X,Y$, we have $(X \circ Y)(x)=X(Y(x))$.

The input is given in the following format.

$N\ K$ $P_1\ P_2\ \cdots\ P_N$

Here, $P_i$ denotes the value of $P(i)$.

Print the number of ordered $K$-tuples satisfying the conditions, modulo $1\,000\,000\,007$.

• $1 \le N \le 200\,000$.
• $1 \le K \le 10^{18}$.
• $P$ is a permutation of $(1,2,\ldots,N)$.