P11362 [NOIP2024] 遗失的赋值

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const int MOD=1e9+7;
const int M=1e5+5;
ll n,m,v,ans,f[M];
struct xz{
	ll c,b;
}x[M];
bool cmp(xz a,xz b){return a.c<b.c;}
ll js;
ll qpow(ll a,ll b){
	if(b==1) return a;
	if(b==0) return 1;
	if(b%2!=0) return qpow(a,b-1)*a;
	js=qpow(a,b/2);
	return js*js;
}
ll fun(ll v,ll x){
	ll ans=0;
	ans+=qpow(v,2*x);
	ans%=MOD;
	ans-=qpow(v,x);
	ans%=MOD;
	ans+=qpow(v,x-1);
	ans%=MOD;
	return ans;
}
void work(){
	ans=1;
	cin>>n>>m>>v;
	for(int i=1;i<=m;i++)	cin>>x[i].c>>x[i].b;
	sort(x+1,x+1+m,cmp);
	for(int i=2;i<=m;i++){
		if(x[i].c==x[i-1].c){
			if(x[i].b!=x[i-1].b){
				cout<<0<<endl;
//				cout<<"QAQ"<<endl;
				return ;
			}
			continue;
		}
		ans*=fun(v,x[i].c-x[i-1].c),ans%=MOD;
	}	
	ans*=qpow(v,2*(x[1].c-1));
	ans*=qpow(v,2*(n-x[m].c));
	cout<<ans<<endl;
	return ;
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int t;
	cin>>t;
	while(t--) work();
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const ll MOD=1e9+7;
const int M=1e5+5;
ll n,m,v,ans,f[M];
struct xz{
	ll c,b;
}x[M];
bool cmp(xz a,xz b){return a.c<b.c;}
ll js;
ll qpow(ll a,ll b){
	if(b==1) return a;
	if(b==0) return 1;
	if(b%2!=0) return qpow(a,b-1)*a%MOD;
	js=qpow(a,b/2)%MOD;
	return js*js%MOD;
}
ll fun(ll v,ll x){
	ll ans=0;
	ans+=qpow(v,2*x);
	ans%=MOD;
	ans+=MOD;
	ans-=qpow(v,x);
	ans%=MOD;
	ans+=qpow(v,x-1);
	ans%=MOD;
	return ans;
}
void work(){
	ans=1;
	cin>>n>>m>>v;
	for(int i=1;i<=m;i++)	cin>>x[i].c>>x[i].b;
	sort(x+1,x+1+m,cmp);
	for(int i=2;i<=m;i++){
		if(x[i].c==x[i-1].c){
			if(x[i].b!=x[i-1].b){
				cout<<0<<endl;
//				cout<<"QAQ"<<endl;
				return ;
			}
			continue;
		}
		ans*=fun(v,x[i].c-x[i-1].c),ans%=MOD;
	}	
	ans*=qpow(v,2*(x[1].c-1))%MOD;
	ans%=MOD;
	ans*=qpow(v,2*(n-x[m].c))%MOD;
	ans%=MOD;
	cout<<ans<<endl;
	return ;
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int t;
	cin>>t;
	while(t--) work();
	return 0;
}