求调

#include <bits/stdc++.h>
using namespace std;
const int M = 100005;
const int Mod = 1000000007;
int n,m,v;//1 <= n <= 1e9 1 <= m <= 1e5 2 <= v <= 1e9
struct Node{
    int c,d;
}a[M];
bool cmp(Node a,Node b)
{
    if (a.c < b.c) return 1;
    return 0;
}
map<int,int> mp;
long long quik(int num)
{
    //cout << num << endl;
    long long ans = 1;
    for (int i = 0; num > 0; i++)
    {
        if ((num & (1 << i))) 
        {
            ans *= mp[(1 << i)];
            //printf("mp[%d]=%d\n",(1<<i),mp[1<<i]);
            ans %= Mod;
            num -= (1 << i);//cout << num << endl;
        }
    }
    //if (ans == 0) cout << "ddfdf" << endl;
    return ans;
}
int main ()
{
    //freopen("assign2.in","r",stdin);
    int T;
    scanf("%d",&T);
    while (T--)
    {
        memset(a,0,sizeof a);
        scanf("%d%d%d",&n,&m,&v);
        //exit(0);
        for (int i = 1; i <= m; i++) scanf("%d%d",&a[i].c,&a[i].d);
        sort(a + 1,a + 1 + m,cmp);
        for (int i = 0; (1ll << i) <= 2 * n; i++)
        {
            if (i == 0) mp[(1 << i)] = v;
            else
            {
                mp[(1 << i)] = (1ll*mp[1 << (i - 1)] * mp[1 << (i - 1)]) % Mod;
                //printf("mp[%d]=%d\n",(1<<i),mp[1<<i]);
            }
        }
        //cout << endl << endl;
        long long ans = quik(2 * (a[1].c - 1));
        //cout << ans << endl;
        for (int i = 1; i <= m; i++)
        {
            while (i + 1 <= m && a[i].c == a[i + 1].c)
            {
                if (a[i].d != a[i + 1].d)
                {
                    ans = 0;
                    break;
                }
                i++;
            }
            if (ans == 0) break;

            if (i + 1 <= m)
            {
                ans *= quik(2 * (a[i + 1].c - a[i].c)) - quik(a[i + 1].c - a[i].c) + quik(a[i + 1].c - a[i].c - 1);
                ans %= Mod;
            }
            else
            {
                ans *= quik(2*(n - a[i].c));
                ans %= Mod;
            }
        }
        printf("%lld\n",ans);
        //exit(0);
    }
    return 0;
}