15分求救

考场上正解3h没调出来，自闭了

#define allLL
#include<bits/stdc++.h>
#define LL long long
#ifdef allLL
#define int LL
const int INF=(1e18);
#else
const int INF=1e9+9;
#endif
#define N 500005
#define P 1000000007
template<typename T>T Max(T x,T y){return (x<y?y:x);}
template<typename T>T Min(T x,T y){return (x<y?x:y);}
template<typename T>void read(T&x){
x=0;char c=getchar();/*T fh=1;*/while(c<'0'||'9'<c){/*if(c=='-')fh=-1;*/c=getchar();}
while('/'<c&&c<':'){x=x*10+(c^'0');c=getchar();}/*x*=fh;*/}
template<typename T>void write(T x){
if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar('0'+x%10);}
using namespace std;
int n,m,v;
pair<int,int> p[N];
struct matx{
    int mp[3][3];
    int n,m;
    int* operator [](int id){return mp[id];}
    matx operator * (matx oth){
        matx c={{},n,oth.m};
//      cout<<n<<','<<m<<","<<oth.m<<"::::::::::::::::::\n";
        for(int i=1;i<=n;i++){
            for(int j=1;j<=oth.m;j++){
                c[i][j]=0;
                for(int k=1;k<=m;k++){
//                  cout<<":::::::::::::"<<mp[i][k]<<"*"<<oth[k][j]<<":\n";
                    c[i][j]=(c[i][j]+mp[i][k]*oth[k][j])%P;
                }
            }
        }
        return c;
    }
};
const matx ii={{{},{0,1,0},{0,0,1}},2,2};
matx qp(matx a,int b){
    if(b==0)return ii;
    if(b==1)return a;
    matx c=qp(a,b>>1);
    if(b&1)return c*c*a;
    else return c*c;
}
#undef int
int main(){
#ifdef allLL
#define int LL
#endif
    int T;
    read(T);
    while(T--){
        read(n);
        read(m);
        read(v);
        for(int i=1;i<=m;i++){
            read(p[i].first);
            read(p[i].second);
        }
        sort(p+1,p+m+1);
        int fl=0;
        for(int i=1;i<m;i++){
            if(p[i].first==p[i+1].first&&p[i].second!=p[i+1].second){
                fl=1;
                break;
            }
        }
        if(fl){
            puts("0");
            continue;
        }
//      if(n<=12){
//          bl::solve();
//          continue;
//      }
        m=unique(p+1,p+m+1)-p-1;
//      cout<<m<<"::::\n"; 
        matx u={{},1,2};
        matx m1={{},2,2};
        matx m2={{},2,2};
        matx m3={{},2,2};

        m1[1][1]=v*v%P;m1[1][2]=0;
        m1[2][1]=(v-1)*v%P;m1[2][2]=v;

        m2[1][1]=0;m2[1][2]=v*v%P;
//      cout<<m2.m<<"::\n";
        m2[2][1]=0;m2[2][2]=(v+(v-1)*(v-1))%P;

        m3[1][1]=0;m3[1][2]=0;
//      cout<<m2.m<<"::\n";
        m3[2][1]=0;m3[2][2]=(v*v-(v-1))%P;
        if(p[1].first==1){
            if(m>1&&p[2].first==2){
                u[1][1]=0,u[1][2]=(v*v-(v-1))%P;
//          cout<<u[1][1]<<','<<u[1][2]<<":::\n";
                for(int i=3;i<=m;i++){
                    if(p[i].first==p[i-1].first+1)u=u*m3;
                    else{
                        if(p[i].first-p[i-1].first-1>0)u=u*qp(m1,p[i].first-p[i-1].first-1);
                        u=u*m2;
                    }
        //          puts("*");
//                  cout<<u[1][1]<<','<<u[1][2]<<":::\n";
                }
                if(p[m].first!=n){
                    u=u*qp(m1,n-p[m].first);
        //          cout<<u[1][1]<<','<<u[1][2]<<":::\n";
                }
            }
            else{
                if(n==1)u[1][1]=0,u[1][2]=1;
                else{
                    u[1][1]=v*v-v,u[1][2]=v%P;
//                  cout<<u[1][1]<<','<<u[1][2]<<":::\n";
                    for(int i=2;i<=m;i++){
                        if(p[i].first==p[i-1].first+1)u=u*m3;
                        else{
                            if(p[i].first-p[i-1].first-1-(i==2)>0)u=u*qp(m1,p[i].first-p[i-1].first-1);
                            u=u*m2;
                        }
            //          puts("*");
//                      cout<<u[1][1]<<','<<u[1][2]<<":::\n";
                    }
                }
                if(p[m].first!=n){
                    if(n>2)u=u*qp(m1,n-p[m].first-1);
//                  cout<<u[1][1]<<','<<u[1][2]<<":::\n";
                }
            }
        }
        else{
            u[1][1]=1,u[1][2]=0;

//          cout<<u[1][1]<<','<<u[1][2]<<":::\n";
            for(int i=1;i<=m;i++){
                if(p[i].first==p[i-1].first+1)u=u*m3;
                else {
                    if(p[i].first-p[i-1].first-1-(i==1)>0)u=u*qp(m1,p[i].first-p[i-1].first-1);
                    u=u*m2;
                }
    //          puts("*");
//              cout<<u[1][1]<<','<<u[1][2]<<":::\n";
            }
            if(p[m].first!=n){
                u=u*qp(m1,n-p[m].first);
    //          cout<<u[1][1]<<','<<u[1][2]<<":::\n";
            }
        }
//      cerr<<":::::";
//      cout<<"*";
        write((u[1][1]+u[1][2])%P);
        puts("");
    }
    return 0;
#undef int
}
/*
10
5 1 2
1 2
*/
/*
1
10 5 2
2 2
3 2
4 2
7 2
10 2

1
10 11 2
10 2
7 2
7 2
2 2
3 2
4 2
10 2
7 2
10 2
3 2
3 2
*/
/*
3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2

*/