AT_kupc2016_j 色塗り

蜜柑的生日快到了，为了给喜欢图论的蜜柑制作一份特别的礼物，阿罗玛决定送她一张无向图。 阿罗玛购入了一张有 $n$ 个顶点和 $n$ 条边的连通无向图。这个图的顶点编号为 $1, 2, \ldots, n$，每个 $i$（$1 \leq i \leq n$）都存在一条边连接顶点 $i$ 和顶点 $a_i$。为了使这份礼物更有创意，阿罗玛决定使用 $k$ 种不同的颜色来为这张图染色，并先算出总共有多少种不同的染色方式。**其中，如果通过重新排列顶点编号可以得到一样的染色方案，则认为是同一种方案，不重复计算。**请计算，用 $k$ 种颜色为图染色的总方案数，并给出结果模 $10^9 + 7$ 的余数。

输入从标准输入给出，格式如下： > $n$ $k$ $a_1$ $\ldots$ $a_n$

请输出一行，表示用 $k$ 种颜色染色图的方案数，并取模 $10^9 + 7$ 的结果。

- $1 \leq n \leq 10^5$ - $1 \leq k \leq 10^5$ - 对于每个 $i$（$1 \leq i \leq n$），$1 \leq a_i \leq n$ - 图是连通的。 - 图中没有自环或重边。 **本翻译由 AI 自动生成**