问题描述

有一个长度为n ，且每个数字等概率取[1, m]之间的整数的随机数组。对它进行一次变换，所有数字x都会变成a[x]，其中a是给定的一个1~n 的排列。

可以证明经过有限次变换后数组一定会变回最初的样子，现在需要知道第一次变回自身所需变换次数的期望。请你输出期望答案乘上m^n 以后模10^9 + 7的结果。

Input

第一行输入包含整数 N,M 。

接下来N个整数表示排列a。

Output

输出一个整数表示答案。

Examples

输入样例1:

2 5 

2 1 4 5 3

输出样例1:

107

输入样例2:

3 5 

1 5 4 3 2

输出样例2:

249

输入样例3:

42 12 

2 1 4 3 6 7 5 9 10 11 12 8

输出样例3:

268468106

Notes

前 20%的测试数据满足 N ≤ 5, M ≤ 10;

前 40%的测试数据满足 N ≤ 1000, M ≤ 20;

前 60%的测试数据满足 N ≤ 1000, M ≤ 50;

前 80%的测试数据满足 N ≤ 10^9 , M ≤ 50;

全部测试数据满足 N ≤ 10^9 , M ≤ 200。