#include<bits/stdc++.h>
using namespace std;
#define mod 1000000009
#define N 1000000009
bool a[N];
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	cin>>T;
	while(T--)
	  {
	  	unsigned long long n,m,v;
	  	cin>>n>>m>>v;
	  	memset(a,0,sizeof(0));
	  	int f=0;
	  	for(int i=1;i<=m;i++)
	  	  {
	  	  	int a1,a2;
	  	  	cin>>a1>>a2;
	  	  	if(a[a1]!=0)
	  	  	  {
	  	  	  	f=1;
				  }
	  	  	a[a1]=1;
			}
		if(f==1)
		  {
		  	cout<<0<<endl;
			continue;
		  }
		unsigned long long s=1;
		for(int i=1;i<n;i++)
		  {
		  	unsigned long long s1=1;
		  	if(a[i+1]==0)
		  	  s1=(v*v)%mod;
		  	else if(a[i+1]!=0)
		  	  {
		  	  	if(a[i]!=0)
		  	  	  s1=((v-1)*v+1)%mod;
		  	  	else
		  	  	  s1=(v*v)%mod;
			  }
		  	s1=s1%mod;
		  	s=(s*s1)%mod;
		  }
		cout<<s<<endl;
	  }
}
