#206 Permutation

Loading problem...

Preparing the statement, recent submissions, and submit form.

#206 Permutation | DOJ

DOJ/MathDOJ/MathDOJ 1

Authors: pk661

Time limit: 3000 ms
Python time limit: 8000 ms
Memory limit: 1024 MB
Checker: DIFF
Solve threshold: 100

Statement

KO EN

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

Input

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

Output

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

Constraints

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

Subtasks

#	Score	Constraints
1	25	$K=1$ .
2	75	No additional constraints.

Samples

Sample 1

Input

3 1
1 2 3

Output

Sample 2

Input

4 2
2 1 4 3

Output

Sample 3

Input

6 2
2 3 1 5 6 4

Output

Editorial

View editorial