#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

*/