Shuffle

Byteasar owns a deck of $n$ cards. The slots that hold the cards are numbered $1$ through $n$. He has practiced one particular shuffle so thoroughly that it always rearranges the deck in exactly the same way: whatever card sits in slot $k$ is moved to slot $a_k$. Because every card lands in a distinct slot, the sequence $a_1, a_2, \dots, a_n$ is a permutation of $1, 2, \dots, n$.

Byteasar applies this same shuffle $l$ times in a row. Write $b_k$ for the slot that ends up holding the card which started in slot $k$. Formally, set $a^{(1)}_k = a_k$ and $a^{(t)}_k = a_{a^{(t-1)}_k}$ for $t \ge 2$; then $b_k = a^{(l)}_k$.

You are told $n$, $l$, and the whole sequence $b_1, b_2, \dots, b_n$. Count how many shuffles are consistent with what Byteasar saw, that is, how many permutations $a$ satisfy $a^{(l)}_k = b_k$ for every $k$. The number of such shuffles can be enormous, so report it modulo $10^9 + 7$. If no shuffle can produce $b$, the answer is $0$.

The first line contains two integers $n$ and $l$ ($1 \le n, l \le 10^6$). Each of the next $n$ lines contains a single integer: the $k$-th of them is $b_k$ ($1 \le b_k \le n$), the slot holding the card from slot $k$ after the shuffle has been repeated $l$ times. The values $b_1, \dots, b_n$ are guaranteed to form a permutation of $1, \dots, n$.

Print one integer: the number of shuffles $a$ (permutations of $1, \dots, n$) for which repeating $a$ exactly $l$ times yields the given sequence $b$, taken modulo $10^9 + 7$. Print $0$ if no such shuffle exists.