45pts 求调

WA on 10~20.

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

typedef long long ll;
const ll maxm = 1e5 + 10, mod = 1e9 + 7;

ll n, m, v, ans;
pair<ll, ll> e[maxm];

ll q_pow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void work() {
    cin >> n >> m >> v;
    for (ll i = 1; i <= m; i++) cin >> e[i].fi >> e[i].se;
    sort(e + 1, e + m + 1);
    ans = q_pow(v, (e[1].fi - 1 + n - e[m].fi) * 2);
    for (ll i = 2; i <= m; i++) {
        if (e[i].fi == e[i - 1].fi) {
            if (e[i].se != e[i - 1].se) {
                ans = 0;
                break;
            } else {
                continue;
            }
        }
        ans *= (q_pow(v, (e[i].fi - e[i - 1].fi) * 2) + mod - q_pow(v, e[i].fi - e[i - 1].fi - 1) * (v - 1) % mod) % mod;
    }
    cout << ans << '\n';
    return;
}

int main() {
    ll T;
    cin >> T;
    while (T--) ans = 0, work();
    return 0;
}