给你一个按照以下方式构建的有向图：

• 选择一个包含恰好 $n$ 个顶点和 $n$ 条边的连通无向图。顶点编号为 $1$ 到 $n$。
• 将每条无向边转换为一条有向边，使得每个顶点的出度均为 $1$。

此外，给你 $m$ 种不同的颜色来对顶点进行染色。你的任务是计算可以制作出的不同染色图的数量。

如果且仅当两个染色图 $A$ 和 $B$ 的顶点集之间存在一个映射 $P$，满足以下约束条件时，这两个染色图被认为是相同的：

• 图 $A$ 中的顶点 $u$ 与图 $B$ 中的顶点 $P(u)$ 具有相同的颜色。
• 对于图 $A$ 中的任意两个不同顶点 $u$ 和 $v$，$P(u)$ 和 $P(v)$ 是图 $B$ 中的不同顶点。
• 对于图 $A$ 中的任意有向边 $u \to v$，图 $B$ 中都存在对应的有向边 $P(u) \to P(v)$。

输出答案模 $10^9 + 7$ 的结果。

输入格式

输入的第一行包含两个空格分隔的整数 $n$ 和 $m$（$3 \le n \le 10^5$，$1 \le m \le 10^9$），分别表示图中的顶点数和拥有的颜色数。

接下来 $n$ 行。第 $i$ 行包含一个整数 $f_i$（$1 \le f_i \le n$，$f_i \ne i$），表示给定图中存在一条从顶点 $i$ 到顶点 $f_i$ 的有向边。

输出格式

输出单行，包含一个整数，表示答案。

样例

输入样例 1

6 3
2
3
4
1
1
3

输出样例 1

378