#include <bits/stdc++.h>
using namespace std;
int n,m,v,T,x[100009],y[100009],t[100009],a[100009],h[100009];
long long inv[20000009],je[20000009];
const int mod=1e9+7;
void an1(){
    for (int i=1;i<=n;i++)a[x[i]]=y[i];
    long long ans=n*n;
    for (int i=1;i<n;i++){
        if (h[a[i]]!=0){
            if (h[a[i]]!=a[i+1])ans--;
        }else{
            h[a[i]]=a[i+1];
            ans-=n-1;
        }
    }
    if (ans<n-1)cout<<0<<"\n";
    else if (ans==n-1)cout<<1<<"\n";
    else cout<<je[ans]*inv[n-1]%mod*inv[ans-n+1]%mod<<"\n";
}
int kp(int a,int b){
    int ans=1;
    while (b>0){
        if (b&1){ans=1ll*ans*a%mod;}
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}
void init(){
    je[0]=1;
    for (int i=1;i<=20000000;i++){
        je[i]=je[i-1]*i%mod;
    }
    inv[20000000]=kp(je[20000000],mod-2);
    for (int i=19999999;i>=1;i--){
        inv[i]=inv[i+1]*(i+1)%mod;
    }
}
int main(){
    freopen("assign.in","r",stdin);
    freopen("assign.out","w",stdout); 
    init();
    cin>>T;
    while (T--){
        cin>>n>>m>>v;
        for (int i=1;i<=m;i++){
            cin>>x[i]>>y[i];
        }
        if (n==m){
            int ok=1;
            for (int i=1;i<=n;i++)t[i]=0,h[i]=0;
            for (int i=1;i<=n;i++){
                if (t[x[i]]!=0){ok=0;break;}
                t[x[i]]=1;
            }
            if (ok)an1();
            else cout<<"1919810\n";
        }else cout<<"114514\n";
    }
    return 0;
}