1805: paleta

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:14 通过:5

题目描述

     小Mirko使用他的空闲时间来绘画。为了这个爱好,他喜欢用刷子和一个含有K种颜色的托盘。他的朋友Slavko决定考考Mirko的智力于是给他一个着色布进行绘画。这个着色布包含了N个像素,编号为1,2,…,N。
     Mirko决定使用他的托盘中K种颜色填满各个像素。但是他更加喜欢彩色的东西。因此他选择了N个数字fi,规定i像素的颜色涂的与fi像素不相同,除非fi=i。当fi=i时若其他条件均满足,在像素i处他可以涂任意他喜欢的颜色。
     Mirko想知道不同的涂Slavko着色布可能的数量,他非常想得到你的帮助。请你计算有多少种可能的方法来涂着色布。输出一行包含一个整数,由于答案可能很大,输出其 mod 1000 000 007 的值即可。

输入格式

第一行包含正整数N,K。
第二行包含N个数字fi。

输出格式

第一行输出被覆盖的长度,精确到小数点后6位。

输入样例 复制

3 4
2 1 1

输出样例 复制

36

数据范围与提示

50%的数据 所有fi均不相同。
100%的数据 N,K≤1000000,1≤fi≤N。