셔플

바이트아사르(Byteasar)는 $n$장의 카드로 이루어진 덱을 가지고 있다. 카드가 놓이는 자리에는 $1$번부터 $n$번까지 번호가 매겨져 있다. 그는 한 가지 셔플 동작을 완벽하게 익혀서, 셔플할 때마다 덱이 항상 똑같은 방식으로 재배열된다. 즉 $k$번 자리에 있던 카드는 언제나 $a_k$번 자리로 옮겨진다. 모든 카드가 서로 다른 자리로 가므로, 수열 $a_1, a_2, \dots, a_n$은 $1, 2, \dots, n$의 순열이다.

바이트아사르가 이 셔플을 연달아 $l$번 반복한다. 처음에 $k$번 자리에 있던 카드가 최종적으로 놓이는 자리를 $b_k$라고 하자. 정확히는 $a^{(1)}_k = a_k$, 그리고 $t \ge 2$에 대해 $a^{(t)}_k = a_{a^{(t-1)}_k}$로 정의하면 $b_k = a^{(l)}_k$이다.

$n$, $l$과 수열 $b_1, b_2, \dots, b_n$ 전체가 주어진다. 이 관찰과 맞아떨어지는 셔플, 즉 모든 $k$에 대해 $a^{(l)}_k = b_k$를 만족하는 순열 $a$가 몇 개인지 세어라. 그 개수가 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다. $b$를 만들어 내는 셔플이 하나도 없으면 답은 $0$이다.

첫째 줄에 두 정수 $n$과 $l$이 주어진다 ($1 \le n, l \le 10^6$). 이어지는 $n$개의 줄 중 $k$번째 줄에는 정수 $b_k$ ($1 \le b_k \le n$)가 하나씩 주어지며, 이는 셔플을 $l$번 반복한 뒤 처음 $k$번 자리에 있던 카드가 놓이는 자리이다. $b_1, \dots, b_n$은 $1, \dots, n$의 순열임이 보장된다.

셔플 $a$(즉 $1, \dots, n$의 순열) 중에서 $a$를 정확히 $l$번 반복했을 때 주어진 수열 $b$가 되는 것의 개수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다. 그런 셔플이 없으면 $0$을 출력한다.