记录编号	598141	评测结果	MMMMMAAAAWWWMMMWMMMM
题目名称	[NOIP 2024]遗失的赋值	最终得分	20
用户昵称	李奇文	是否通过	未通过
代码语言	C++	运行时间	6.782 s
提交时间	2025-01-15 07:59:59	内存使用	310.55 MiB

#include<bits/stdc++.h>
using namespace std;
long long mod=1e9+7;
long long T,n,m,v,q,ans;
struct node{
    int c,d;
}e[100005];
bool cmp(node a,node b){
    if(a.c!=b.c){
        return a.c<b.c;
    }
    return a.d<b.d;
}
int ksm(long long a,long long b){
    if(!b) return 1ll;
    long long c=ksm(a,b>>1);
    c=c*c%mod;
    if(b&1){
        c=c*a%mod;
    }
    return c;
}
int main(){
    freopen("assign.in","r",stdin);
    freopen("assign.out","w",stdout);
    std::cin>>T;
    while(T--){
        q=0,ans=0;
        std::cin>>n>>m>>v;
        for(int i=1;i<=m;i++){
            std::cin>>e[i].c>>e[i].d;
        }
        sort(e+1,e+1+m,cmp);
        for(int i=1;i<m;i++){
            if(e[i].c==e[i+1].c&&e[i].d!=e[i+1].d){
                q=1;
            }        
        }
        if(q){
            cout<<0<<endl;
            continue;
        }
        ans=ksm(v,(e[1].c-1)*2);
        for(int i=1;i<m;i++){
            if(e[i].c==e[i+1].d){
                continue;
            }
            ans*=ans*(ksm(v,2*(e[i+1].c-e[i].c))-ksm(v,e[i+1].c-e[i].c-1)*(v-1)%mod+mod)%mod;           
        }
        ans=ans*ksm(v,(n-e[m].c)*2)%mod;
        std::cout<<ans<<endl;
    }
    return 0;    
}