#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define N 2001000
ll T,n,m,range,c[N],d[N],req[N],ans,val[N],cval[N];
bool bz[N],fg,subA,ok;
pair<ll,ll>lim[N];
template<typename T>inline void read(T &x)
{
    bool f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=!f;ch=getchar();}
    while(ch>='0'&&ch<='9'){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;
}
ll ksm(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void check(ll x)
{
    if(x==n+1)
    {
        for(int i=1;i<n;i++)
        {
            if(val[i]==lim[i].first&&val[i+1]!=lim[i].second) return;
        }
        ok=1;
        return;
    }
    else
    {
        if(val[x])
        {
            check(x+1);
            if(ok) return;
        } 
        else
        {
            for(int i=1;i<=range;i++)
            {
                val[x]=i;
                check(x+1);
                if(ok) return;
                val[x]=0;
            }
        }
    }
}
void dfs(ll x)
{
    if(x==n)
    {
        ok=0;
        for(int i=1;i<=n;i++) val[i]=cval[i];
        check(1);
        if(ok) ans=(ans+1)%mod;
        return;
    }
    else
    {
        for(int i=1;i<=range;i++)
        {
            for(int j=1;j<=range;j++)
            {
                lim[x]={i,j};
                dfs(x+1);
                lim[x]={0,0};
            }
        }
    }
}
int main()
{
    freopen("assign.in","r",stdin);
    freopen("assign.out","w",stdout);
    read(T);
    while(T--)
    {
        ans=0;
        subA=0;
        read(n),read(m),read(range);
        for(int i=1;i<=m;i++)
        {
            read(c[i]),read(d[i]);
            if(c[i]!=i) subA=1;
        } 
        if(m==n&&!subA)
        {
            ans=((range*(range-1)%mod)+1)%mod;
            ans=ksm(ans,n-1);
            write(ans);
            putchar('\n');
            continue;
        }
        else if(m==1)
        {
            ans=ksm(range*range%mod,n-1);
            write(ans);
            putchar('\n');
            continue;
        }
        else if(n<=12&&m<=12)
        {
            fg=0;
            for(int i=1;i<=n;i++) bz[i]=val[i]=0;
            for(int i=1;i<=m;i++)
            {
                if((bz[c[i]]&&d[i]!=val[c[i]])||d[i]>range)
                {
                    fg=1;
                    break;
                }
                val[c[i]]=d[i],bz[c[i]]=1;
            } 
            if(fg)
            {
                puts("0");
                continue;
            }
            for(int i=1;i<=n;i++) cval[i]=val[i];
            dfs(1);
            write(ans);
            putchar('\n');
        }
        else
        {
            puts("0");
        }
    }
    return 0;
}