小 Mirko 闲暇时喜欢画画。在这个爱好中，他喜欢使用画笔和一个包含 $K$ 种颜色的调色盘。他的朋友 Slavko 决定利用 Mirko 的才能，给了他一本新的涂色书让 Mirko 涂色。这本涂色书包含 $N$ 幅插图，编号为 $1, 2, \dots, N$。

Mirko 决定用调色盘中 $K$ 种颜色中的恰好一种来为每幅插图着色。然而，他非常喜欢色彩斑斓的东西。他选择了 $N$ 个数字 $f_i$，并决定将编号为 $i$ 的插图涂成与编号为 $f_i$ 的插图不同的颜色，除非 $f_i = i$。如果 $f_i = i$，这意味着只要满足所有其他条件，他可以将编号为 $f_i$ 的插图涂成他喜欢的任何颜色。

Mirko 想知道有多少种可能的方法来为 Slavko 的涂色书着色，他非常需要你的帮助！请计算为涂色书着色的可能方法数。由于输出可能非常大，请输出答案模 $1\,000\,000\,007$ 的结果。

输入格式

输入的第一行包含正整数 $N, K$ ($1 \le N, K \le 1\,000\,000$)。

第二行包含 $N$ 个整数 $f_i$ ($1 \le f_i \le N$)，即文中提到的数字。

输出格式

输出的第一行也是唯一一行，应包含为 Slavko 的涂色书着色的可能方法数模 $1\,000\,000\,007$ 的结果。

子任务

在占总分 50% 的测试数据中，所有数字 $f_i$ 将互不相同。

样例

输入格式 1

2 3
2 1

输出格式 1

6

输入格式 2

3 4
2 3 1

输出格式 2

24

输入格式 3

3 4
2 1 1

输出格式 3

36

输入格式 4

3 4
1 1 2

输出格式 4

36

说明

样例 1 解释：Mirko 有三种颜色，并决定编号为 2 的插图不能与编号为 1 的插图颜色相同。可能的着色方案为 $(1, 2)$、$(1, 3)$、$(2, 1)$、$(2, 3)$、$(3, 1)$、$(3, 2)$，其中括号中的第一个数字表示第一幅插图的颜色，第二个数字表示第二幅插图的颜色。

样例 4 解释：Mirko 有四种颜色。对于第一幅插图没有限制，可以涂成任何颜色。第二幅插图必须与第一幅不同，第三幅插图必须与第二幅不同。这意味着这两幅插图可以用剩下的 3 种颜色着色。这使我们总共有 $4 \times 3 \times 3 = 36$ 种组合。