가환 제곱근

양의 정수 $N$, $K$와 $(1,2,\ldots,N)$의 순열 $P$가 주어진다.

$(1,2,\ldots,N)$의 순열 $A_1,A_2,\ldots,A_K$로 이루어진 순서 있는 $K$-튜플 중, 다음 조건을 모두 만족하는 것의 개수를 $1\,000\,000\,007$로 나눈 나머지를 구하여라.

• 모든 $1 \le i \le K$에 대해 $A_i \circ A_i = P$이다.
• 모든 $1 \le i,j \le K$에 대해 $A_i \circ A_j = A_j \circ A_i$이다.

여기서 순열의 합성은 함수 합성으로 정의한다. 즉, 두 순열 $X,Y$에 대해 $(X \circ Y)(x)=X(Y(x))$이다.

입력은 다음과 같은 형식으로 주어진다.

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

$P_i$는 $P(i)$의 값을 의미한다.

조건을 만족하는 순서 있는 $K$-튜플의 개수를 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

• $1 \le N \le 200\,000$.
• $1 \le K \le 10^{18}$.
• $P$는 $(1,2,\ldots,N)$의 순열이다.