题目描述

Mirko 有 $k$ 种颜色和 $n$ 个图像需要上色。图像编号从 $1$ 到 $n$，他决定用 $k$ 种颜色中的一种来填充每个图像。

为此，他选择了 $n$ 个数字 $f_i$，并决定按照如下方法涂色：

• 若 $f_i\ne i$，则图像 $i$ 与图像 $f_i$ 的颜色不应该相同。
• 若 $f_i=i$，他可以在满足所有其他条件的基础上，将图像 $f_i$ 涂成任何颜色。

你需要求出上色的可能方法的数量。

由于输出可能非常大，你只需要输出答案对 $\bm{10^9+7}$ 取模后的结果。

输入格式

第一行两个整数 $n,k$，表示图像的数量与颜色的数量。

接下来 $n$ 行，即 $f_i$。

输出格式

仅一行一个整数，即给书着色的可能方法的数量对 $10^9+7$ 取模后的结果。

2 3
2 1

6

3 4
2 3 1

24

3 4
2 1 1

36

3 4
1 1 2

36

提示

样例 1 说明

共有 $3$ 种颜色，并且图像 2 的颜色不能与图像 1 相同。可能的上色方案为 $(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)$，其中括号中两个数字分别表示两个图像的颜色。

样例 4 说明

共有 $4$ 种颜色。

• 对于图像 1，可以涂成任何颜色。
• 对于图像 2，颜色不能与图像 1 相同。
• 对于图像 3，颜色不能与图像 2 相同。

即图像 2 可以用除了图象 1 外的 $3$ 种颜色着色，图像 3 可以用除了图象 2 外的 $3$ 种颜色着色。

答案为 $4\times 3\times 3=36$。

数据规模与约定

• 对于 $50\%$ 的数据，有 $f_i\ne f_j(1\le i\ne j\le n)$。
• 对于 $100\%$ 的数据，有 $1\le n,k\le 10^6$。

对于所有合法的 $f_i$，有 $1\le f_i\le n$。

来源

本题译自 COCI2013-2014 CONTEST 2 T5 PALETA。

按照原题数据配置，本题满分 $140$ 分。