#include<bits/stdc++.h>
using namespace std;

#define int long long

const int P=1e9+7,N=1e5+5;

int T,n,m,v;
int c[N],d[N];
unordered_map<int,int> mp;

int qpow(int a,int b)
{
    int c=1;
    for(;b;b>>=1,a=a*a%P)
        if(b&1)
            c=c*a%P;
    return c;
}

inline int rd()
{
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())
        if(ch=='-')
            f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())
        x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}

void wt(const int &x)
{
    if(x<0)
        return putchar('-'),wt(-x),void();
    if(x>9)
        wt(x/10),putchar(x%10+48);
    else
        putchar(x+48);
}

namespace A
{
    int a[100],b[100];
    int e[N],f[N];
    void sol(){
        if(v==1)
            return puts("1"),void();
        int ans=0;
        for(int i=1;i<=n;i++)
            e[i]=mp[i];
        for(int ste=0;ste<(1ll<<(2*(n-1)));ste++){
            for(int i=1;i<n;i++){
                if((ste>>(2*i-1))&1) a[i]=1;
                else a[i]=2;
                if((ste>>(2*i-2))&1) b[i]=1;
                else b[i]=2;
            }
            for(int i=1;i<=n;i++) f[i]=e[i];
            bool isok=1;
            for(int i=1;i<n;i++){
                if(!f[i]||f[i]!=a[i])
                    continue;
                if(f[i+1]&&f[i+1]!=b[i])
                    {isok=0;break;}
                else if(!f[i+1])
                    f[i+1]=b[i];
            }
            ans+=isok;
        }
        wt(ans),putchar('\n');
    }
} // namespace A

namespace B
{
    void sol(){
        int bs=(v*(v-1)%P+v)%P;
        wt(qpow(bs,n-1)),putchar('\n');
    }
} // namespace B

namespace C
{
    bool vis[N];
    bool check(){
        if(n!=m) return 0;
        for(int i=1;i<=n;i++) vis[i]=0;
        for(int i=1;i<=m;i++){
            if(vis[c[i]])
                return 0;
            vis[c[i]]=1;
        }
        return 1;
    }
    void sol(){
        int bs=((v-1)*v%P+1)%P;
        wt(qpow(bs,n-1)),putchar('\n');
    }
} // namespace C

void solve()
{
    // remember to clear!!
    mp.clear();
    n=rd(),m=rd(),v=rd();
    bool flg=1;int cnt=0;
    for(int i=1,p,k;i<=m;i++){
        c[i]=rd(),d[i]=rd();
        p=c[i],k=d[i];
        if(mp.count(p)==0)
            mp[p]=k,++cnt;
        else if(mp[p]!=k)
            flg=0;
    }
    if(!flg)
        return puts("0"),void();
    if(n<=12)
        return A::sol(),void();
    if(cnt==1)
        return B::sol(),void();
    if(C::check())
        return C::sol(),void();
}

signed main()
{
    freopen("assign.in","r",stdin);
    freopen("assign.out","w",stdout);
    T=rd();
    while(T--)
        solve();
    return 0;
}