#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int T , n , m , v , c[N] , d[N] , x[N] , ans;
bool f;

void dfs(int now , int ai , int bi , int lst)
{
	if(x[now] && lst && x[now] != lst)
	{
		return;
	}
	if(now == n - 1)
	{
		if(lst == ai && x[now + 1] && x[now + 1] != bi) return;
		ans ++;
		ans %= mod;
		return;
	}
	if(lst == ai)
	{
		for(int i = 1 ; i <= v ; i ++)
		{
			for(int j = 1 ; j <= v ; j ++)
				dfs(now + 1 , i , j , bi);
		}
	}else{
		for(int i = 1 ; i <= v ; i ++)
		{
			for(int j = 1 ; j <= v ; j ++)
				dfs(now + 1 , i , j , 0);
		}
	}
}

void init()
{
	f = 0;
	ans = 0;
	for(int i = 0 ; i <= n + 2 ; i ++)
	{
		x[i] = 0;
	}
}

int main()
{
	freopen("assign.in" , "r" , stdin);
	freopen("assign.out" , "w" , stdout);
	cin >> T;
	while(T --)
	{
		cin >> n >> m >> v;
		init();
		for(int i = 1 ; i <= m ; i ++)
		{
			cin >> c[i] >> d[i];
			if(x[c[i]] && x[c[i]] != d[i])
			{
				f = 1;
			}
			x[c[i]] = d[i];
		}
		if(f)
		{
			cout << 0 << endl;
			continue;
		}
		for(int i = 1 ; i <= v ; i ++)
		{
			for(int j = 1 ; j <= v ; j ++)
				dfs(1 , i , j , 0);
		}
		cout << ans % mod << endl; 
	}
	return 0;
}
