45pts快速幂WA求条

疑似ksm的取模有问题

前9个点能过，数一大就WA

求条

#include <bits/stdc++.h>
using namespace std;
const long long mo=1000000007;
struct shu1{
    long long hao,shu;
}a[100005];
bool cmp(shu1 x,shu1 y){
    return x.hao<y.hao;
}
long long ksm(long long a1,long long b1,long long p1){
    long long ans=1;
    a1%=p1;
    while(b1){
        if(b1%2){
            ans=(ans*a1)%p1;
        }
        b1/=2;
        a1=(a1*a1)%p1;
    }
    return ans;
}
long long t,n,m,v;
int main(){
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>n>>m>>v;
        for(int j=1;j<=m;j++){
            cin>>a[j].hao>>a[j].shu;
        }
        sort(a+1,a+m+1,cmp);
        int c=0;
        for(int i1=2;i1<=m;i1++){
            if(a[i1].hao==a[i1-1].hao&&a[i1].shu!=a[i1-1].shu){
                c=1;
                break;
            }
        }
        if(c==1){
            cout<<0<<endl;
            continue;
        }
        long long ans=ksm(v*v,n-1,mo);
        for(int i1=2;i1<=m;i1++){
            if(a[i1].hao==a[i1-1].hao) continue;
            else{
                long long feifa=ksm(v,a[i1].hao-a[i1-1].hao+1,mo);
                ans=ans*(feifa-(v-1))/feifa;
                ans%=mo;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}