Impostors

There are $N$ rooms in a row and $N$ impostors such that initially (at second $t = 0$), the impostor $i$ is in room $i$. From room $i$, there is a directed vent to room $p_i$, such that no two vents have the same destination (forming a permutation of integers from $1$ to $N$). The impostors move in the following way: the impostor who was in room $i$ at second $t$ will move ("vent") to room $p_i$ at second $t + 1$.

After $K$ seconds you can track where each impostor is: the $i^{th}$ is in room $q_i$. Now, you wonder: how many vent configurations (permutations $p$) can lead to this? Since the answer can be very large, output it modulo $10^9 + 7$. Note that your tracking device might be faulty, so the answer can be $0$.

Task

Write a program that, knowing $N, K$ and the position of each impostor after $K$ seconds, calculates how many possible vent permutations exist.

Input Data

The first line of input contains two integers $N$ and $K$.

The second line contains $N$ integers $q_i$ ($1 \leq q_i \leq N$), representing the positions of the impostors after $K$ seconds. It is guaranteed that $q$ forms a permutation of integers from $1$ to $N$.

Output Data

The output consists of one integer: the number (modulo $10^9 + 7$) of permutations $p$, such that after $K$ seconds, impostor $i$ would be in room $q_i$ for each $i$.

Restrictions

• $2 \leq N \leq 10^5$
• $2 \leq K \leq 10^{18}$.

Example 1

stdin

3 3
1 2 3

stdout

3

The valid permutations $p$ are $(1, 2, 3), (2, 3, 1)$ and $(3, 1, 2)$.

Example 2

stdin

5 2
3 1 5 4 2

stdout

0