Congratulation
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
问题描述
有一个长度为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。
