#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
const int N=1e6+10;
const int Mod=1e9+7;
int n,k;
vector<int> vec[N];
int t[N];
int g[N];
int mem[N],l=1;
int dfs(int s,int root)
{
	if(mem[s]!=0)
	{
		if(mem[root]<=mem[s]) return l-mem[s];
		return 0;
	}
	
	mem[s]=l;
	l++;
	return dfs(t[s],root);
}
long long poww(int x,int y)
{
	long long sum=1;
	for(int i=1;i<=y;i++)
	{
		sum*=x%Mod;
		sum%=Mod;
	}
	return sum;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&t[i]);
		//d[t]++;
		vec[i].push_back(t[i]);
	}
	g[0]=1;
	g[1]=k;
	g[2]=(k-1)*k%Mod;
	g[3]=g[2]*(k-2)%Mod;
	for(int i=4;i<=n;i++)
	{
		g[i]=((k-2)*g[i-1]%Mod+((k-1)*g[i-2])%Mod)%Mod;
	}
	long long ans=1; 
	int suml=0;
	for(int i=1;i<=n;i++)
	{
		
		if(mem[i]==0)
		{
			//memset(mem,0,sizeof(mem));
			int awa=dfs(i,i);
			//cout<<awa<<endl;
			ans=(1ll*ans*g[awa])%Mod;
			suml+=awa;
		} 
		
	}
	//cout<<ans<<endl;
	printf("%lld",ans*poww((k-1),(n-suml))%Mod);
	return 0;
}
//f[i][j][k] f[i+1]j[k/