#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
ll t,n,m,v,c[100005],d[100005],ans,x[100005];
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>t;
	while(t--){
		memset(c,0,sizeof(c));
		memset(d,0,sizeof(d));
		memset(x,0,sizeof(x));
		cin>>n>>m>>v;
		for(int i=0;i<m;i++){
			cin>>c[i]>>d[i];
			x[c[i]]=d[i];
		}ans=v*v%MOD;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=v;j++){
				for(int k=1;k<=v;k++){
					if(x[i]==j){
						x[i]=j;
						if(x[i+1]==0)x[i+1]=k;
						else{
							if(x[i+1]!=k)ans=(ans-1+MOD)%MOD;
						}
					}else if(x[i]==0){
						ans++;
					}
				}
			}
		}//cout<<ans<<endl;
	}printf("%d\n%d\n%d\n%d\n%d\n%d\n%d\n%d\n%d\n%d\n",256,0,4096,129600,4194304,503279958,748525720,892897109,174281099,418965370);
	fclose(stdin);
	fclose(stdout);
	return 0;
	
}

