本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-20 14:28:40

Div.2 C 级别唐氏题，考场上为什么调了 3h+ 还没调出来呢？连 newbie 都能场切这题，我真的是 CM 吗？

首先排序去重，如果遇到条件自己冲突的那方案数就是 $0$。

按照已经确定的点将原序列 $n$ 个位置划分为若干段，除了首段全部由不确定位置组成以外，每一段开头都是一个确定的位置。

• 首段不确定位置
  这一段的 $a,b$ 随便填，只需要让 $x_i \neq a_i$，那么就显然是合法的。
• 除了首段，最后一段以外的段
  这类段的特点是第一个位置是确定的，段最后的下一个位置也是确定的。
  段的 $a,b$ 方案书可以通过总方案数减去不合法方案数得到，令长度为 $l$。
  总方案数是 $v^{2l}$。
  不合法方案如何构造呢？显然只能是本段通过一些 $a,b$ 的构造，强迫下一个确定位置的 $x$ 值不等于其给定值。
  第一个位置有 $v$ 的方案数确定第二个位置的值，第二个位置同样有 $v$ 的方案数确定第三个位置的值。
  以此类推，总共有 $v^{len-1}$ 的方案数确定本段最后一个位置的值。 本段最后一个位置总共有 $v-1$ 的方案数（$a$ 值等于自己，$b$ 值不等于下一个位置）。 所以，总的不合法方案数是 $v^{len-1}(v-1)$。 总合法方案数是 $v^{2len}-v^{len-1}(v-1)$。
• 最后一段
  显然 $a,b$ 随便填。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x\/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
const ll mod=1e9+7;
int n,m,v;
pii lim[100005];
ll qpow(ll a,ll b){
\/\/	printf("qpow %lld %lld\n",a,b);
	ll ret=1;
	for(;b;a=a*a%mod,b>>=1){
		if(b&1)ret=ret*a%mod;
	}
\/\/	printf("ret %lld\n",ret);
	return ret;
}
void solve(int id_of_test){
	read(n);
	read(m);
	read(v);
	FOR(i,1,m){
		read(lim[i].fi);
		read(lim[i].se);
	}
	sort(lim+1,lim+m+1);
	m=unique(lim+1,lim+m+1)-lim-1;
	FOR(i,1,m-1){
		if(lim[i].fi==lim[i+1].fi){
			if(lim[i].se!=lim[i+1].se){
				puts("0");
				return;
			}
		}
	}
	ll ans=1;
	ans=ans*qpow(v,2*(lim[1].fi-1));
	ans=ans*qpow(v,2*(n-lim[m].fi))%mod;
	FOR(i,1,m-1){
		ll res=qpow(v,2*(lim[i+1].fi-lim[i].fi));
	\/\/	printf("pre %lld [%d,%d]\n",res,lim[i].fi,lim[i+1].fi);
		res-=qpow(v,lim[i+1].fi-lim[i].fi-1)*(v-1)%mod;
	\/\/	printf("fff %lld\n",res);
		ans=ans*res%mod;
	}
	printf("%lld\n",(ans+mod)%mod);
}
int main()
{
	int T;
	read(T);
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}