#include<bits/stdc++.h>
using namespace std;
char buf[1<<20],*it1,*it2;
#define Open_File(x) FILE *Fin=freopen(#x".in","r",stdin),*Fout=freopen(#x".out","w",stdout);
#define Close() fclose(Fin),fclose(Fout);
#define gch() (it1==it2&&(it2=(it1=buf)+fread(buf,1,1<<16,stdin),it1==it2)?EOF:*it1++)
template<typename T>istream&operator<<(istream& input,T& n){
if(typeid(n)==typeid(int)||typeid(n)==typeid(long long)){
bool m;m=n=0;
char c=gch();
while(!isdigit(c))m^=c=='-',c=gch();
while(isdigit(c))n=(n<<1)+(n<<3)+(c^48),c=gch();
n=(m?-n:n);
}else input>>n;
return input;
}
#define int long long
const int N=200005,mod=1e9+7;
int power(int n,int m){
int ans=1;
while(m){
if(m&1)ans=ans*n%mod;
m>>=1;
n=n*n%mod;
}
return ans;
}
int T,n,m,v,a[N],ans,b[N],c[N];
void dfs(int k){
if(k>=n)return ans+=1-(a[k-1]&&a[k-1]==b[k-1]&&a[k]!=c[k-1]),void();
if(a[k-1]&&a[k-1]==b[k-1]){
if(a[k]){
if(a[k]==c[k-1]){
b[k]=c[k]=1,dfs(k+1);
b[k]=c[k]=2,dfs(k+1);
b[k]=1,c[k]=2,dfs(k+1);
b[k]=2,c[k]=1,dfs(k+1);
}else return;
}else{
a[k]=c[k-1];
b[k]=c[k]=1,dfs(k+1);
b[k]=c[k]=2,dfs(k+1);
b[k]=1,c[k]=2,dfs(k+1);
b[k]=2,c[k]=1,dfs(k+1);
a[k]=0;
}
}else{
b[k]=c[k]=1,dfs(k+1);
b[k]=c[k]=2,dfs(k+1);
b[k]=1,c[k]=2,dfs(k+1);
b[k]=2,c[k]=1,dfs(k+1);
}
return;
}
signed main(){
FILE* Fin=freopen("assign.in","r",stdin);
FILE* Fout=freopen("assign.out","w",stdout);
cin<<T;
while(T--){
cin<<n<<m<<v,ans=0;
if(m==1){
for(int i=1,x,y;i<=m;i++)cin<<x<<y;
cout<<power(v*v%mod,n-1)<<'\n';
continue;
}else{
for(int i=1;i<=n;i++)a[i]=b[i]=c[i]=0;
bool fl=0;
for(int i=1,x,y;i<=m;i++){
cin<<x<<y;
if(a[x]&&a[x]!=y)fl=1;
a[x]=y;
}
if(fl==1){cout<<0<<'\n';continue;}
dfs(1);
cout<<ans<<'\n';
}
}
return 0;
}