#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#define cl(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
const db pi=3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862;
void gn(int &x){
    int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')sg=-1,x=0;else x=c-'0';
    while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';
    x*=sg;
}
void gn(ll &x){
    int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')sg=-1,x=0;else x=c-'0';
    while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';
    x*=sg;
}
int mo=1000000007;
int inf=1000000000;
db eps=1e-6;
//ll inf=1000000000000000000ll;
int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
#define x1 x192837465
#define x2 x123456789
#define y1 y192837465
#define y2 y123456789



int n,k;
int to[111];
int vis[111];
int mar[111];
int cnt[111];
void detec(int r){
    int u=r;
    int len=0;
    while(mar[u]!=r){
        mar[u]=r;
        u=to[u];
        ++len;
    }
    if(u==r){
        cnt[len]++;
    }
}
int main(){
    int _tes;
    gn(_tes);
    while(_tes--){
        gn(n);gn(k);
        cl(vis);
        cl(mar);
        cl(cnt);
        for (int i=1;i<=n;i++)gn(to[i]),to[i]++;
        for (int i=1;i<=n;i++)detec(i);
        int lef=n;
        int ans=1;
        for (int i=1;i<=n;i++){
            lef-=cnt[i];
            cnt[i]/=i;
            int an=(0ll+qp(k-1,i)+(k-1)*qp(-1,i))%mo;
            ans=1ll*ans*qp(an,cnt[i])%mo;
        }ans=1ll*ans*qp(k-1,lef)%mo;
        ans=(ans+mo)%mo;
        printf("%d\n",ans);
    }
    return 0;
}