#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
int n,m,v,c[100005],d[100005];
//istream&operator>>(istream&in,int &i){
//	static char ch;
//	ch=in.get(),i=0;
//	while(!isdigit(ch))ch=in.get();
//	do i=(i<<1)+(i<<3)+(ch^48),ch=in.get();while(isdigit(ch));
//	return in;
//}
//ostream&operator<<(ostream&out,const int &i){
//	if(9<i)out<<i/10;
//	return out<<(signed)i%10;
//}
inline int fast_pow(int x,int y){
	int ans(1);
	x%=mod;
	while(y){
		if(y&1)(ans*=x)%=mod;
		(x*=x)%=mod,y>>=1;
	}
	return ans;
}
inline void Main(){
	cin>>n>>m>>v;
	int c,d;
	map<int,int>mp;
	for(int i=1;i<=m;i=-~i){
		cin>>c>>d;
		if(mp.find(c)!=mp.end()){
			if(mp[c]==d){
				--i,--m;
				continue;
			}
			for(++i;i<=m;i=-~i)cin>>c>>d;
			cout<<"0\n";
			return;
		}
		mp[c]=d;
	}
//	cout<<fast_pow(v*v,n-m)*fast_pow(v*v-v+1,m-1)%mod<<'\n';
//	return;
	int ans(1);
	int _=0,__=0,___=0,sum=0;
	(ans*=fast_pow(v*v,mp.begin()->first-1))%=mod;
	for(map<int,int>::iterator i=mp.begin();i!=mp.end();++i){
		c=i->first,d=i->second;
		map<int,int>::iterator temp(i);
		++temp;
		if(temp!=mp.end()){
			int cc=temp->first;
			if(c+1==cc){
				_=1;
				(ans*=(v*v-v+1)%mod)%=mod;
			}else{
				__=1;
				if(cc==n){
					(ans*=fast_pow(v*v,n-c-1))%=mod;
					(ans*=(v*v-v+1)%mod)%=mod;
					break;
				}
				(ans*=fast_pow(v*v,cc-c))%=mod;
				(ans*=(v*v-v+1)%mod)%=mod;
			}
		}else{
			___=1,(ans*=fast_pow(v*v,n-c))%=mod;
			break;
		}
	}
	cout<<((ans-sum)%mod+mod)%mod<<' '<<_<<' '<<__<<' '<<___<<'\n';
}
signed main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	cin>>T;
	while(T--)Main();
	return 0;
}
