矩阵离奇的负数

我用的是矩阵加速优化DP，但是官方第二组数据就出现了离奇的负数

#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;
}

我感觉每个矩阵都是取过模的，不知道为什么会有很大的数字来撑爆long longQAQ