考虑按照每个一元限制进行分段。每一段计算答案。

对于可以包含 $x$ 个二元限制的区间(长度为 $x+1$ 且左右端点都存在一元限制的区间)，考虑计算方案数。

定义这样的方案有 $f_x$ 种。分情况讨论。

• 如果第一个二元限制的第一个数和属于他的一元限制一样，那么这一位的二元限制总共有 $v$ 种放法，且下一位也有了限制，方案数是 $f_{x-1}\times v$。

• 否则怎么填都可以，方案数 $v\times (v-1)$

综上所述 $f_x = f_{x-1}\times v+v\times (v-1)$。

边界 $f_1 = v\times (v-1)+1$。即第一个数和左边的数相等的一种情况以及不相等的情况。

对于开头的一段，没有最初的限制，对于最后的一段，没有结尾的限制，所以这两段方案数都是 $v^{2x}$。

然后矩阵快速幂加速递推即可

发现这个递推其实并没有很难，化简一下就会发现 $f_x = v^{k} \times f_{x-k} + v^{2x} - v^{2x-k}$。

带入 $k=x-1$ 就可以快速幂直接求啦。

时间复杂度 $O(Tm(\log m + \log n))$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
const int Mod = 1e9+7;
int T,n,m,v,ans;
struct node{
    int id,val;
} a[N];
bool cmp(node a,node b){
    return a.id<b.id;
}
int QuickPower(int x,int k){
    int ans = 1, base = x;
    while(k){
        if(k&1) (ans*=base)%=Mod;
        (base*=base)%=Mod;
        k>>=1;
    }
    return ans;
}
int calc(int x){
    int tmp = QuickPower(v,2*x);
    tmp -= QuickPower(v,x);
    tmp += QuickPower(v,x-1);
    tmp%=Mod;
    tmp+=Mod;
    tmp%=Mod;
    return tmp;
}
signed main(){
    cin>>T;
    while(T--){
        cin>>n>>m>>v;
        ans = 1;
        for(int i = 1; i<=m; i++){
            cin>>a[i].id>>a[i].val;
        }
        sort(a+1,a+1+m,cmp);
        int flag = 0;
        for(int i = 2; i<=m; i++){
            if(a[i].id==a[i-1].id && a[i].val!=a[i-1].val){
                flag=1;
                break;
            } else if(a[i].id==a[i-1].id) continue;
            (ans *= calc(a[i].id-a[i-1].id))%=Mod;
        }
        (ans *= QuickPower(v,2*(a[1].id-1)))%=Mod;
        (ans *= QuickPower(v,2*(n-a[m].id)))%=Mod;
        if(flag) {
            cout << 0 << endl;
        } else{
            cout << ans << endl;
        }
     }
    return 0;
}