#include <bits/stdc++.h>

typedef long long ll;
typedef std::pair<int, int> pii;

template<typename T>
void read(T &r) { static char ch, last; ch = getchar(), last = 'z', r = 0; while (ch < '0' || ch > '9') last = ch, ch = getchar(); while (ch >= '0' && ch <= '9') r = (r << 1) + (r << 3) + (ch ^ 48), ch = getchar(); r = last == '-' ? -r : r; }
template<typename T, typename ...Ts>
void read(T &r, Ts& ...args) { read(r), read(args...); }

const int N = 1e5 + 10, p = 1e9 + 7;
int n, m, v;
int c[N], d[N];

namespace sub1 {
    int p[13];
    int a[13], b[13];
    int f[N][13];
    int check(int i, int j) {
        for (int x = 1; x < n; x++) {
            a[x] = (i >> (x - 1) & 1) + 1;
            b[x] = (j >> (x - 1) & 1) + 1;
        }
        for (int i = 1; i <= v; i++) f[1][i] = 1;
        if (~p[1]) {
            for (int i = 1; i <= v; i++)
                if (i != p[1]) f[1][i] = 0;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= v; j++) f[i + 1][j] = 0;
            for (int j = 1; j <= v; j++) {
                if (j == a[i]) f[i + 1][b[i]] |= f[i][j];
                else {
                    for (int k = 1; k <= v; k++) f[i + 1][k] |= f[i][j];
                }
            }
            if (~p[i + 1]) {
                for (int j = 1; j <= v; j++) {
                    if (j != p[i + 1]) f[i + 1][j] = 0;
                }
            }
        }
        bool flag = 0;
        for (int i = 1; i <= v; i++) flag |= f[n][i];
        return flag;
    }
    void solve() {
        memset(p, -1, sizeof(p));
        for (int i = 1; i <= m; i++) {
            if ((~p[c[i]]) && p[c[i]] != d[i]) {
                puts("0"); return;
            }
            p[c[i]] = d[i];
        }
        int ans = 0;
        for (int i = 0; i < (1 << n - 1); i++) {
            for (int j = 0; j < (1 << n - 1); j++) {
                ans += check(i, j);
            }
        }
        printf("%d\n", ans);
    }
}

namespace sub2 {
    bool check() {
        for (int i = 1; i <= m; i++) if (c[i] != i) return false;
        return true;
    }
    void solve() {
        ll ans = 1;
        for (int i = 1; i < m; i++) ans *= (1 + 1ll * (v - 1) * v) % p, ans %= p;
        printf("%lld\n", ans);
    }
}

int main() {
    freopen("assign.in", "r", stdin);
    freopen("assign.out", "w", stdout);

    int T;
    read(T);
    while (T--) {
        read(n, m, v);
        for (int i = 1; i <= m; i++) read(c[i], d[i]);
        if (v == 2) sub1::solve();
        else if (m == n && sub2::check()) sub2::solve();
        else puts("0");
    }
    return 0;
}