P7752 [COCI 2013/2014 #2] PALETA

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$ 取模后的结果。

#### 样例 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](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 2](https://hsin.hr/coci/archive/2013_2014/contest2_tasks.pdf) _T5 PALETA_。** 按照原题数据配置，本题满分 $140$ 分。