16 TLE 1.02s，其余也有两个点跑了 900+ms。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 100005, p = 1e9 + 7;

int fpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) (res *= a) %= p;
        (a *= a) %= p;
        b >>= 1;
    }
    return res;
}

int inv(int a) {
    return fpow(a, p - 2);
}

int n, m, v, len, illegal, sum[N];
map<int, int> f;

struct node { int x, y; } a[N];

void solve() {
    f.clear();
    illegal = len = 0;
    cin >> n >> m >> v;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        if (f.count(x) && f[x] != y) illegal = 1;
        f[x] = y;
    }
    if (illegal) {
        cout << 0 << endl;
        return;
    }
    for (auto [x, y] : f)
        a[++len] = {x, y};
    int res = 1;
    for (int i = 1; i <= len; i++) {
        if (i == 1) {
            sum[i] = inv(fpow(v, a[i].x + a[i + 1].x));
            continue;
        }
        int tot = fpow(v, 2 * (a[i].x - a[1].x));
        res = tot - fpow(v, 2 * a[i].x - 1) * sum[i - 1] % p * (v - 1) % p;
        res = (res % p + p) % p;
        sum[i] = sum[i - 1] + res % p * inv(fpow(v, a[i].x + a[i + 1].x)) % p;
        sum[i] %= p;
    }
    cout << res * fpow(v, 2 * (n - a[len].x)) % p * fpow(v, 2 * (a[1].x - 1)) % p << endl;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}