#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,a[100005],b[100005],c[100005];
int n,m,v,ans;
void dfs(int now)
{
	if(now==n)
	{
		bool fu=false;
		for(int i=1;i<=n-1;i++)
		{
			if(c[i]==0||c[i+1]==0||c[i]!=a[i]) continue;
			if(c[i]==a[i]&&c[i+1]==b[i])
			{
				fu=false;
			}
			else {
			fu=true;
			break;
			}
		}
		if(!fu)
		{
			ans++;
		}
		return;
	}
	for(int i=1;i<=v;i++)
	{
		a[now]=i;
		for(int j=1;j<=v;j++)
		{
			b[now]=j;
			dfs(now+1);
		}
	}
}
signed main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>T;
	while(T--)
	{
		memset(c,0,sizeof(c));
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		bool flag=false;
		ans=0;
		cin>>n>>m>>v;
		for(int i=1;i<=m;i++)
		{
			int u;
			cin>>u;
			if(c[u]!=0)
			flag=true;
			cin>>c[u];
		}
		if(m==1)
		{
			ans=1;
			for(int i=1;i<=n;i++)
			{
				ans=(v*ans)%1000000009;
				}	
				cout<<ans<<endl;
		}
		else
		{
			
		if(flag) ans=0;
		else
		dfs(1);
		cout<<ans;
		}
		
	}
	return 0;
 } 
