#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
const ll mod=1e9+7;
int T,m,g;
bool ddd;
ll n,v,ans,now,dp[1010][1010];
struct node{
	ll c,d;
}a[N];
map<ll,int> q;
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m>>v;
		ddd=0;
		for(int i=1;i<=m;i++){
			cin>>a[i].c>>a[i].d;
			if(q[a[i].c]&&q[a[i].c]!=a[i].d) ddd=1;
			else q[a[i].c]=a[i].d;
		}
		m=g;
		if(ddd){
			cout<<0<<"\n";
			for(int i=1;i<=m;i++) q[a[i].c]=0;
			continue;
		}
		ans=0;
		dp[0][1]=1;
		memset(dp,0,sizeof dp);
		for(int i=1;i<=v;i++) dp[1][i]=1;
		for(int i=1;i<n;i++){
			for(int j=1;j<=v;j++){
				for(int k=1;k<=v;k++){
					if(k==q[i]&&q[i+1]&&j!=q[i+1]){
						continue;
					}
					else dp[i+1][j]=(dp[i+1][j]+dp[i][k])%mod;
				}
			}
		}
		for(int i=1;i<=m;i++) q[a[i].c]=0;
		for(int i=1;i<=v;i++) ans=(ans+dp[n][i])%mod;
		cout<<ans<<"\n";
	}
	return 0;
} 
