echipe

You are the owner of a football team. You have found the perfect strategy to win any match your team will play. This strategy consists of instructing each player to pass the ball to exactly one person. Although it initially seems like a poor strategy, it has helped you reach the finals of the village championship.

Within a team, sub-teams are formed. A sub-team is a group of players in which any player can pass to any other player through an indirect pass or a series of passes. In these sub-teams you have established certain roles that at least one player must have, specifically $K$ different roles.

Task

Knowing that there are $N$ players on the team, $K$ different roles, and each pass that a player can make, determine the number of ways to assign roles to the team.

Input data

The first line of the input file echipe.in contains $N$ followed by $K$. The next line contains a sequence of natural numbers $p_1$, $p_2$, $\cdots$, $p_N$. For each $i$, $1 \leq i \leq N$, player $i$ can pass to player $p_i$.

Output data

The first line of the output file echipe.out will contain a single integer, representing the remainder of the number of ways to assign roles to the team divided by $10^9 + 7$.

Constraints and clarifications

• $1 \leq K \leq N \leq 200\ 000$
• Each number in the interval $[1, N]$ appears in the sequence $p$ only once
• It is guaranteed that there is at least one way to assign roles to the team

Subtasks

Example

echipe.in

5 2
2 3 1 5 4

echipe.out

12

Explanation

The formed sub-teams are: $\{ \texttt{1, 2, 3} \}$ and $\{ \texttt{4, 5} \}$.

The passes the players will make look like this, and the ways to assign roles are as follows (where $r_i$ indicates the role of player $i$):