#include <cstdio>
#include <numeric>
#include <iostream>
#include <algorithm>

const double EPS = 1e-7;
const double PI = 3.1415926535897932384626;

const int MAXN = 101;
const int MAXM = 2222;
const int MOD = 1000000007;

struct Edge{
    int node, next;
}e[MAXM];

int T, n, k, t, h[MAXN], deg[MAXN];

void addEdge(int x, int y) {
    deg[x]++;
    deg[y]++;
    t++; e[t] = (Edge){y, h[x]}; h[x] = t;
    t++; e[t] = (Edge){x, h[y]}; h[y] = t;
}

int fpm(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret = 1ll * ret * a % MOD;
        a = 1ll * a * a % MOD;
    }
    return ret;
}

int getCir(int n) {
    int ret = fpm(k - 1, n);
    if (n & 1) ret -= k - 1;
    else ret += k - 1;
    ret %= MOD;
    return ret;
}

int main() {
    std::cin >> T;
    for (int cs = 1; cs <= T; cs++) {
        std::cin >> n >> k;
        t = 0;
        std::fill(h + 1, h + n + 1, 0);
        std::fill(deg + 1, deg + n + 1, 0);
        for (int i = 1; i <= n; i++) {
            int x;
            std::cin >> x;
            addEdge(i, ++x);
        }
        int left = 0, right = 0, answer = 1;
        static int q[MAXN];
        static bool v[MAXN], cir[MAXN];
        std::fill(v + 1, v + n + 1, false);
        std::fill(cir + 1, cir + n + 1, false);
        for (int i = 1; i <= n; i++)
            if (deg[i] == 1) {
                q[++right] = i;
                v[i] = true;
                answer = 1ll * answer * (k - 1) % MOD;
            }
        while (left < right) {
            left++;
            for (int i = h[q[left]]; i; i = e[i].next) {
                if (v[e[i].node]) continue;
                if (--deg[e[i].node] == 1) {
                    v[q[++right] = e[i].node] = true;
                    answer = 1ll * answer * (k - 1) % MOD;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            if (v[i] || cir[i]) continue;
            left = 0, right = 0;
            cir[q[++right] = i] = true;
            while (left < right) {
                left++;
                for (int i = h[q[left]]; i; i = e[i].next) {
                    if (v[e[i].node]) continue;
                    if (cir[e[i].node]) continue;
                    cir[q[++right] = e[i].node] = true;
                }
            }
            answer = 1ll * answer * getCir(right) % MOD;
        }
        std::cout << answer << std::endl;
    }
    return 0;
}