矩阵离奇的负数

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
map<int, int> mp;
int n, m, v;
struct Mat {
	ll a[3][3];
	Mat() {
		memset(a, 0, sizeof(a));
	}
	Mat operator*(const Mat &b)const {
		Mat res;
		for (int i = 1; i < 3; ++i)
			for (int j = 1; j < 3; ++j)
				for (int k = 1; k < 3; ++k)
					res.a[i][j] = (res.a[i][j] + (a[i][k] % mod) * (b.a[k][j] % mod) % mod) % mod;//这里如果不在每个元素后加mod的话就会爆long long(屏幕输出调出来的)
		/*printf("\n");
		for (int i = 1; i < 3; ++i) {
			for (int j = 1; j < 3; ++j)
				printf("%lld ", a[i][j]);
			printf("\n");
		}
		for (int i = 1; i < 3; ++i) {
			for (int j = 1; j < 3; ++j)
				printf("%lld ", b.a[i][j]);
			printf("\n");
		}
		for (int i = 1; i < 3; ++i) {
			for (int j = 1; j < 3; ++j)
				printf("%lld ", res.a[i][j]);
			printf("\n");
		}*/
		return res;
	}
} basx, basy, ans, bas_y;
void mulx(int t) {
	bas_y = basy;
	while (t > 0) {
		if (t & 1)
			ans = ans * bas_y;
		bas_y = bas_y * bas_y;
		t >>= 1;
	}
	return;
}
int main() {
	freopen("assign2.in", "r", stdin);
	freopen("1.out", "w", stdout);
	int T, x, y, lst;
	bool vis;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d", &n, &m, &v);
		mp.clear();
		vis = true;
		for (int i = 1; i <= m; ++i) {
			scanf("%d%d", &x, &y);
			if (mp[x] && mp[x] != y)
				vis = false;
			mp[x] = y;
		}
		if (!vis) {
			printf("0\n");
			continue;
		}
		if (mp[1])
			ans.a[1][1] = 0ll, ans.a[1][2] = 1ll;
		else
			ans.a[1][1] = 1ll, ans.a[1][2] = 0ll;
		basx.a[1][2] = 1ll * v * v, basx.a[2][2] = 1ll * v * (v - 1) + 1ll;
		basy.a[1][1] = 1ll * v * v, basy.a[2][1] = 1ll * v * (v - 1), basy.a[2][2] = 1ll * v;
		lst = 1;
		for (auto to : mp) {
			x = to.first;
			if (x == 1)
				continue;
			mulx(x - lst - 1);
			lst = x;
			ans = ans * basx;
		}
		mulx(n - lst);
		printf("%lld\n", (ans.a[1][1] + ans.a[1][2]) % mod);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}