测评记录

#include <bits/stdc++.h>
using namespace std;
const int p=1e9+7;
int n,m,v;
map<int,int> mp;
long long ans;
long long fast(long long a1,long long b1){
	long long res=1,a=a1,b=b1;
	while(b){
		if(b&1) res=(res%p*a%p)%p;
		a=(a%p*a%p)%p;
		b=b>>1;
	}
	return res%p;
} 
int main(){
//	freopen("assign3.in","r",stdin);
//	freopen("assign333.out","w",stdout);
	int T;
	cin>>T;
	while(T--){
		mp.clear();
		ans=1;
		cin>>n>>m>>v;
		if(n==1) {
			cout<<0<<endl;
			continue;
		}
		int f1=0,f2=0,k=0;
		if(m==n) f2=1;
		for(int i=1;i<=m;i++)
		{
			int id,val;
			cin>>id>>val;
			if(id!=i) f2=0;
			if(mp[id]&&mp[id]!=val) {
				f1=1;break;
			}
			mp[id]=val;
		}
		if(f1){
			cout<<0<<endl;
			continue;
		}
		if(f2){
			ans=1ll*v*(v-1)%p;
			cout<<fast(ans+1,n-1)%p<<endl;
			continue;
		}
		int pos;
		for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++)
		{
			if(it==mp.begin()){
				pos=(*mp.begin()).first;
				ans*=fast(v,2*(pos-1));
			}
			else{
				int d=(*it).first-pos;
				ans=ans*(((fast(v,2*d)-fast(v,d))%p+fast(v,d-1))%p)%p;
				pos=(*it).first;
			}
		}
		pos=(*mp.rbegin()).first;
		ans=ans*fast(v,2*(n-pos))%p;
		cout<<ans<<endl;
	}
}