#include<bits/stdc++.h>
using namespace std;
#define LL long long
const LL MAXN=1e5+5,MOD=1e9+7;
LL n,m,v,c[MAXN],d[MAXN];
unordered_map<LL,LL>num;
template<typename T>inline void read(T &x){
    bool f=1;x=0;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=!f;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?x:-x;return ;
}
template<typename T>inline void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');return ;
}
inline LL ksm(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1){
            res=res*x%MOD;
        }
        x=x*x%MOD;
        y>>=1;
    }
    return res;
}
void solve1(){
    LL ans=ksm(v%MOD,(2*n-2)%(MOD-1))%MOD;
    write(ans);
    putchar('\n');
}
LL a[MAXN],b[MAXN],xx[MAXN],anss;
void dfs(LL x){
    if(x==n){
        for(LL i=1;i<=n;i++)xx[i]=0;
        bool flag=true;
        for(LL i=1;i<n;i++){
            if(num[i]){
                if(!xx[i])xx[i]=num[i];
                else if(xx[i]!=num[i]){
                    flag=false;
                    break;
                }
            }
            if(xx[i]){
                if(a[i]==xx[i]){
                    xx[i+1]=b[i];
                }
            }
        }
        if(num[n]&&xx[n]&&num[n]!=xx[n]){
            flag=false;
        }
        if(flag){
            anss++;
        }
        return ;
    }
    for(LL i=1;i<=v;i++){
        for(LL j=1;j<=v;j++){
            a[x]=i;b[x]=j;
            dfs(x+1);
        }
    }
}
void solve2(){
    anss=0;
    dfs(1);
    write(anss);putchar('\n');
}
void solve3(){
    LL ans=ksm((v*v%MOD-(v-1)%MOD+MOD)%MOD,(m-1)%(MOD-1))%MOD;
    write(ans);putchar('\n');
}
int main(){
    freopen("assign.in","r",stdin);
    freopen("assign.out","w",stdout);
    // double tim=clock();
    LL T;
    scanf("%lld",&T);
    for(LL tst=1;tst<=T;tst++){
        num.clear();
        read(n);read(m);read(v);
        bool flag=true;
        bool flga=true,flgb=true;
        if(n!=m)flga=false;
        for(LL i=1;i<=m;i++){
            read(c[i]);read(d[i]);
            if(!num[c[i]]){
                num[c[i]]=d[i];
            }else{
                if(num[c[i]]!=d[i]){
                    flag=false;
                }
            }
            if(c[i]!=i){
                flga=false;
            }
            if(d[i]!=1){
                flgb=false;
            }
        }
        if(!flag){
            printf("0\n");
            continue;
        }
        if(m==1){
            solve1();
            continue;
        }
        if(n<=12){
            solve2();
            continue;
        }
        if(flga){
            solve3();
            continue;
        }
        solve3();
    }
    // cerr<<(double)(clock()-tim)/CLOCKS_PER_SEC;
}