Permutation

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 satisfying all of the following conditions, modulo .

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

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$

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