Mirko's Image Coloring

Mirko has \(k\) colors and \(n\) images numbered from \(1\) to \(n\). He wants to color each image using one of the \(k\) colors. He chooses \(n\) numbers \(f_i\) (\(1 \le i \le n\)) and colors the images as follows:

• If \(f_i \neq i\), then the color of image \(i\) must be different from the color of image \(f_i\).
• If \(f_i = i\), no additional constraint is imposed for image \(i\) (besides those coming from other images).

Your task is to calculate the number of valid colorings modulo \(10^9+7\). In other words, if the total number of valid ways is \(X\), output \(X \bmod (10^9+7)\).

Explanation

Consider an undirected graph where each image is a vertex. For every \(i\) such that \(f_i \neq i\), add an edge between vertex \(i\) and vertex \(f_i\) (ignoring duplicate edges). The problem reduces to counting the number of proper colorings of this graph with \(k\) colors, i.e., adjacent vertices must have different colors.

Each connected component of the graph can be of two types:

• Tree component: If the component is a tree with \(r\) vertices then the number of colorings is \( k\cdot (k-1)^{r-1} \).
• Cyclic component: If the component contains exactly one cycle with \(c\) vertices and there are \(r\) vertices in total (the remaining \(r-c\) form trees attached to the cycle), the number of colorings is \( \Bigl[(k-1)^c + (-1)^c (k-1)\Bigr]\cdot (k-1)^{r-c} \).

The final answer is the product of the counts for each connected component, taken modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(k\) — the number of images and the number of colors, respectively.

The second line contains \(n\) integers \(f_1, f_2, \dots, f_n\), where \(f_i\) is the number chosen for image \(i\). It is guaranteed that \(1 \le f_i \le n\).

outputFormat

Output one integer: the number of valid colorings modulo \(10^9+7\).

sample

3 3
1 1 3

18