思路与算法

把已知赋值按位置排序，重复位置冲突立即为0，同值合并。两相邻固定位置相距d时，合法的遗失(a,b)选择数为v^(2d)-v^(d-1)*(v-1)。最前固定点之前与最后固定点之后的边各自由贡献v²；各段相乘模1e9+7。指数用快速幂。

正确性说明

从一个固定值出发，对已选的每条蕴含x_i=a_i则x_(i+1)=b_i，可到达值集合不是单点就是全体；当v≥2时，一旦全体就会永远全体，因为可选一个不等于a_i的前值。只有始终单点并最终被迫错值才失败：首a被起始值确定，接下来d-1个中间b任取v种，后续a被迫匹配，最后b有v-1个错误值，所以失败数v^(d-1)(v-1)。从全部v^(2d)减去得到段公式；v=1时也成立。不同固定点间约束只共享已固定端点，独立相乘；两端自由区可反向/正向选变量，总能满足，全部边对合法。

复杂度

每组O(m log m+m log n)时间、O(m)空间，含排序、去重和临时数组初始化；逐组处理，不假定题面未给的总T界。

易错点

统计的是遗失的(a,b)方案，不是变量x的见证数量；同一边对有多组x只能计一次。重复位置冲突样例必须输出0。模减法先加模，n与v可达1e9。

参考代码（C++11）

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

const long long MOD = 1000000007;
long long power(long long a, long long n) {
    long long r = 1;
    for (; n; n /= 2, a = a * a % MOD)
        if (n & 1)
            r = r * a % MOD;
    return r;
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        long long n, v;
        int m;
        cin >> n >> m >> v;
        map<long long, long long> fixed;
        bool ok = true;
        for (int i = 0; i < m; i++) {
            long long c, d;
            cin >> c >> d;
            if (fixed.count(c) && fixed[c] != d)
                ok = false;
            fixed[c] = d;
        }
        if (!ok) {
            cout << 0 << "\n";
            continue;
        }
        long long ans = 1, used = 0, last = -1;
        for (auto x : fixed) {
            if (last >= 0) {
                long long gap = x.first - last;
                used += gap;
                long long ways =
                    (power(v, 2 * gap) - power(v, gap - 1) * (v - 1) % MOD + MOD) % MOD;
                ans = ans * ways % MOD;
            }
            last = x.first;
        }
        ans = ans * power(v, 2 * (n - 1 - used)) % MOD;
        cout << ans << "\n";
    }
}