AT_kupc2016_j.色塗り

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

蜜柑的生日快到了，为了给喜欢图论的蜜柑制作一份特别的礼物，阿罗玛决定送她一张无向图。

阿罗玛购入了一张有 $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
```
4 2
2
3
1
1
```
输出#1
```
12
```
输入#2
```
4 4
2
3
4
1
```
输出#2
```
55
```
输入#3
```
10 5
2
3
4
1
1
1
2
3
3
4
```
输出#3
```
926250
```

说明/提示

$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 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页