#include <bits/stdc++.h>

using namespace std;

#define MAXN 100010
#define MOD 1000000007

int l[MAXN];
unsigned long long ans;
int n,m,v;

void dfs(vector<int> sa,vector<int> sb,int must) {
    int sz = sa.size();
    // Check
    if (sz>0) {
        if (sa[sz-1]==must&&l[sz]!=-1&&sb[sz-1]!=l[sz]) {
            return;
        }
        if (sa[sz-1]!=must) must=-1;
        else must=sb[sz-1];
        if (l[sz]!=-1) must=l[sz];
    }
    if(sz==n-1) {
        ans++;
        return;
    }
    sa.push_back(2);
    sb.push_back(1);
    dfs(sa,sb,must);
    sa[sz]=1;
    sb[sz]=2;
    dfs(sa,sb,must);
    sa[sz]=1;
    sb[sz]=1;
    dfs(sa,sb,must);
    sa[sz]=2;
    sb[sz]=2;
    dfs(sa,sb,must);
}

int main() {
    freopen("assign.in","r",stdin);
    freopen("assign.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T>0) {
        ans = 0;
        cin >> n >> m >> v;
        bool autopass = false;
        for (int i=0; i<n; i++) {
            l[i]=-1;
        }
        for (int i=0; i<m; i++) {
            int a,b;
            cin >> a >> b;
            a--;
            if (l[a]!=-1&&l[a]!=b) autopass = true;
            l[a]=b;
        }
        if (autopass) {
            cout << 0 << endl;
            T--;
            continue;
        }
        // S1
        if (v<=2) {
            if (v==1) {
                cout << 1 << endl;
                T--;
                continue;
            }
            vector<int> sa,sb;
            dfs(sa,sb,-1);
            cout << (ans%MOD) << endl;
            T--;
            continue;
        }
        cout << "WA" << endl;
        T--;
    }
}
