大体思路：分别处理头尾，中间乘上每个连续段的情况。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
struct node
{
	int c,d;
}a[100010];
bool cmp(node a,node b)
{return a.c<b.c;}
int qpow(int x,int y)
{
	int ans=1,a=x;
	while(y>0)
	{
		if(y&1)ans=ans*a%p;
		a=a*a%p;y/=2;
	}
	return ans;
}
signed main()
{
	int t;cin>>t;
	while(t--)
	{
		int n,m,v,flag=1,ans=1;
		cin>>n>>m>>v;
		for(int i=1;i<=m;i++)cin>>a[i].c>>a[i].d;
		sort(a+1,a+m+1,cmp);
		for(int i=1;i<=m;i++)
			if(a[i].c==a[i-1].c&&a[i].d!=a[i-1].d)
			{cout<<0<<endl;flag=0;}
		if(flag)
		{
			for(int i=2;i<=m;i++)
			{
				int l=a[i].c-a[i-1].c;
				ans=ans*(qpow(v,2*l)-qpow(v,l)+qpow(v,l-1))%p;
			}
			ans=(ans*qpow(v,2*(a[1].c-1))%p)*qpow(v,2*(n-a[m].c));
			cout<<ans%p<<endl;
		}
	}
}

提交记录