TLE on #8#9#15#16#19#20

且这几个测试点在洛谷 5s 都跑不完

求原因

#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;
int T, n, m, brk, c[100010], ctop;
long long v, ans, unic[100010];
long long pw(long long base, long long time) {
	if(time == 0) return 1ll;
	long long res = (pw(base, time / 2) * pw(base, time / 2)) % 1000000007;
	if(time & 1) res = (res * base) % 1000000007; 
	return res;
}
int main() {
    cin >> T;
    while(T--) {
        cin >> n >> m >> v;
        ctop = brk = 0;
        unordered_map<int, int> pl;
        for(int i = 1; i <= m; i++) {
            int d;
            cin >> c[i] >> d;
            if(pl.count(c[i]) && pl[c[i]] != d)
                brk = 1;
            pl[c[i]] = d;
        }
        if(brk) {
            cout << 0 << endl;
            continue;
        }
        sort(c + 1, c + m + 1);
        for(int i = 1; i <= m; i++) {
            if(i == 1 || c[i] != c[i - 1]) {
                unic[++ctop] = 1ll * c[i];
            }
        }
        ans = pw(v, 2 * (unic[1] - 1));
        for(int i = 2; i <= ctop; i++) {
            if(unic[i - 1] == unic[i] - 1) {
                ans *= (((v * v) % 1000000007) - v + 1 + 1000000007);
                ans %= 1000000007;
            } else {
                ans *= (((pw(v, 2 * (unic[i] - unic[i - 1])) - pw(v, unic[i] - unic[i - 1] - 1) * (v - 1)) % 1000000007) + 1000000007);
                ans %= 1000000007;
            }
        }
        if(unic[ctop] != n) ans *= pw(v, 2 * (n - unic[ctop]));
        ans %= 1000000007;
        cout << ans << endl;
    }
    return 0;
}