#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define N 1000005
int T;
int n,m,v;
int c[N],d[N];
int a[N],b[N];
int num[N],Num[N];
int ans;
int ksm(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
void dfs(int step)
{
    if(step==2*n-1)
    {
        for(int i=1;i<=n;i++)Num[i]=num[i];
        for(int i=1;i<n;i++)b[i]=a[n+i-1];
        for(int i=1;i<n;i++)
        {
            if(Num[i]==a[i])
            {
                if(Num[i+1]>0&&Num[i+1]!=b[i])return ;
                Num[i+1]=b[i];
            }
        }
        ans++;
        if(ans>=mod)ans-=mod;
        return ;
    }
    for(int i=1;i<=v;i++)
    {   
        a[step]=i;
        dfs(step+1);
    }
}
void work1()
{
    memset(num,0,sizeof(num));
    for(int i=1;i<=m;i++)
    {
        if(num[c[i]]>0&&num[c[i]]!=d[i])
        {
            printf("0\n");
            return ;
        }
        num[c[i]]=d[i];
    }
    ans=0;
    dfs(1);
    printf("%lld\n",ans);
    return ;
}
void work2()
{
    printf("%lld\n",ksm(v,(n*2-2)%(mod-1)));
    return ;
}
void work3()
{
    printf("%lld\n",ksm((v*v-v+1)%mod,n-1));
    return ;
}
int g[N];
int fac[N];
unordered_map<int,int>vis;
int C(int n,int m)
{
    if(m>n)return 0;
    return fac[n]*ksm(fac[m],mod-2)%mod*ksm(fac[n-m],mod-2)%mod;
}
void work4()
{
    vis.clear();
    int M=0;
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    for(int i=1;i<=m;i++)if(!vis[c[i]])M++,vis[c[i]]=1;
    for(int i=1;i<=n;i++)g[i]=ksm((v*v-v+1)%mod,i-1);
    int Ans=0;
    if(M==n)printf("%lld\n",g[n]);
    else if(M==1)printf("%lld\n",ksm(v,(n*2-2)%(mod-1)));
    else
    {
        for(int i=n;i>=M;i--)(Ans+=C(n-m,i-M)*g[i]%mod)%=mod;
        printf("%lld\n",Ans);
    }
}
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c))
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
void solve()
{
    n=read(),m=read(),v=read();
    int flg=0,flg2=0;
    for(int i=1;i<=m;i++){c[i]=read(),d[i]=read();if(c[i]!=i)flg=1;if(d[i]!=1)flg2=1;}
    if(v<=2)
    {
        work1();
        return ;
    }
    if(m==1)
    {
        work2();
        return ;
    }
    if(!flg&&m==n)
    {
        work3();
        return ;
    }
    if(!flg2)
    {
        work4();
        return ;
    }
}
signed main()
{
    freopen("assign.in","r",stdin);
    freopen("assign.out","w",stdout);
    T=read();
    while(T--)solve();
}