#include<bits/stdc++.h>
#define ll long long
namespace solve{
	inline ll read(){
		ll tmp=1,f=0;
		char a=getchar();
		while(a<'0' or a>'9')tmp=a=='-'?-1:tmp,a=getchar();
		while(a>='0' and a<='9')f=(f<<3)+(f<<1)+(a^48),a=getchar();
		return tmp*f;
	}
	inline void write(ll x){
		if(x<0)putchar('-'),x=-x;
		if(x>9)write(x/10);
		putchar(x%10+'0');
	}
	const int N=1e6+5,mod=1e9+7;
	int n,m,v,f[N],now[N],x[N],all,cnt,ans;
	struct limit{
		int c,d;
		inline bool operator<(const limit &x)const{return c<x.c;}
	}q[N];
	std::map<int,int>mp;
	inline void dfs(int u,int val){
		if(u==n+1)return ans=(ans+val)%mod,void();
		if(x[u])return now[u]=x[u],dfs(u+1,val);
		if(mp.find(now[u-1])!=mp.end()){
			now[u]=mp[now[u-1]],dfs(u+1,val);
			for(int i=1;i<=v;i++){
				if(i==mp[now[u-1]])continue;
				now[u]=i,dfs(u+1,val+1);
			}
		}else{
			for(int i=1;i<=v;i++)now[u]=i,dfs(u+1,val+1);
		}
	}
	void main(){
		freopen("assign.in","r",stdin);
		freopen("assign.out","w",stdout);
		for(int T=read();T;T--){
			n=read(),m=read(),v=read(),ans=cnt=0;
			std::memset(f,0,sizeof(f));
			mp.clear();
			for(int i=1;i<=m;i++)q[i].c=read(),q[i].d=read(),x[q[i].c]=q[i].d;
			std::sort(q+1,q+m+1);
			for(int i=1;i<m;i++){
				if(q[i].c+1==q[i+1].c)
					mp[q[i].d]=q[i+1].d;
			}
			dfs(1,0);
			write(ans),putchar('\n');
		}
		return;
	}
}
int main(){
	solve::main();
	return 0;
}
/*

*/
