#include<iostream>
using namespace std;
const long long mod=1e9+7;
long long dp[100010][2],k;
int c[100010],n,T,vis[100010];
int main()
{
cin>>T;
while(T--)
{
cin>>n>>k;
dp[1][0]=0,dp[1][1]=1;
for(int i=2; i<=n; i++)
{
dp[i][0]=(dp[i-1][0]*(k-2)%mod+dp[i-1][1]*(k-1)%mod)%mod;
dp[i][1]=dp[i-1][0];
}
memset(vis,-1,sizeof(vis));
for(int i=0; i<n; ++i) cin>>c[i];
int sum=0; long long ans=1;
for(int i=0; i<n; ++i)
{
if(vis[i]!=-1)continue;
int t=i;
while(vis[t]==-1)
{
vis[t]=i;
t=c[t];
}
if(vis[t]!=i)continue;
int tmp=0,u=t;
do{
++tmp;
t=c[t];
}while(t!=u);
ans=ans*(dp[tmp][0]*k%mod)%mod;
sum+=tmp;
}
sum=n-sum;
for(int i=0;i<sum;++i) ans=ans*(k-1)%mod;
cout<<ans<<endl;
}
}
/*
3
3 3
1 2 0
4 3
1 2 0 0
3 2
1 2 0
*/