Control Car (Hard Version)

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

const ll MOD = 1000000007LL;
const ll INV4 = 250000002LL;
const ll INV16 = 562500004LL;

const int UP = 0;
const int DOWN = 1;
const int LEFT = 2;
const int RIGHT = 3;

using Matrix = vector<vector<ll>>;

ll modPow(ll a, long long e) {
    ll r = 1;
    while (e > 0) {
        if (e & 1LL) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1LL;
    }
    return r;
}

void addMod(ll &x, ll y) {
    x += y;
    if (x >= MOD) x -= MOD;
}

int id(int row, int dir) {
    return (row - 1) * 4 + dir;
}

bool bottomOpen(int b, int c) {
    return b != RIGHT && c != LEFT;
}

bool rightOpen(int a, int c) {
    return a != DOWN && c != UP;
}

pair<Matrix, vector<ll>> buildTransfer(int n, bool lastColumn) {
    int S = 4 * n;
    Matrix go(S, vector<ll>(S, 0));
    vector<ll> good(S, 0);

    for (int sr = 1; sr <= n; sr++) {
        for (int so = 0; so < 4; so++) {
            int from = id(sr, so);
            vector<array<ll, 4>> dp(n + 2);
            for (auto &v : dp) v.fill(0);

            auto addL = [&](int r, int b, ll w) {
                ll each = w * INV16 % MOD;
                for (int a = 0; a < 4; a++) {
                    for (int c = 0; c < 4; c++) {
                        if (bottomOpen(b, c)) {
                            if (r < n) addMod(dp[r + 1][c], each);
                        } else if (rightOpen(a, c)) {
                            if (!lastColumn) addMod(go[from][id(r, c)], each);
                        } else {
                            addMod(good[from], each);
                        }
                    }
                }
            };

            auto addU = [&](int r, int aKnown, ll w) {
                ll each = w * INV16 % MOD;
                for (int b = 0; b < 4; b++) {
                    for (int c = 0; c < 4; c++) {
                        if (bottomOpen(b, c)) {
                            if (r < n) addMod(dp[r + 1][c], each);
                        } else if (rightOpen(aKnown, c)) {
                            if (!lastColumn) addMod(go[from][id(r, c)], each);
                        } else {
                            addMod(good[from], each);
                        }
                    }
                }
            };

            addL(sr, so, 1);
            for (int r = sr + 1; r <= n; r++) {
                for (int a = 0; a < 4; a++) {
                    if (dp[r][a]) addU(r, a, dp[r][a]);
                }
            }
        }
    }

    return {go, good};
}

int groupOf(int pos, int n) {
    int S = 4 * n;
    return pos == S ? n : pos / 4;
}

int groupStart(int group, int n) {
    return group == n ? 4 * n : 4 * group;
}

Matrix multiplyMatrix(const Matrix &A, const Matrix &B, int n) {
    int N = (int)A.size();
    Matrix C(N, vector<ll>(N, 0));

    for (int i = 0; i < N; i++) {
        int gi = groupOf(i, n);
        for (int k = groupStart(gi, n); k < N; k++) {
            ll aik = A[i][k];
            if (!aik) continue;

            int gk = groupOf(k, n);
            for (int j = groupStart(gk, n); j < N; j++) {
                if (!B[k][j]) continue;
                C[i][j] = (C[i][j] + aik * B[k][j]) % MOD;
            }
        }
    }

    return C;
}

vector<ll> multiplyVector(const vector<ll> &v, const Matrix &M, int n) {
    int N = (int)v.size();
    vector<ll> res(N, 0);

    for (int i = 0; i < N; i++) {
        if (!v[i]) continue;

        int gi = groupOf(i, n);
        for (int j = groupStart(gi, n); j < N; j++) {
            if (!M[i][j]) continue;
            res[j] = (res[j] + v[i] * M[i][j]) % MOD;
        }
    }

    return res;
}

ll solveCase(int n, long long m) {
    int S = 4 * n;
    int N = S + 1;

    auto [baseGo, baseGood] = buildTransfer(n, false);
    Matrix trans(N, vector<ll>(N, 0));
    for (int i = 0; i < S; i++) {
        for (int j = 0; j < S; j++) trans[i][j] = baseGo[i][j];
        trans[i][S] = baseGood[i];
    }
    trans[S][S] = 1;

    vector<ll> cur(N, 0);
    for (int dir = 0; dir < 4; dir++) cur[id(1, dir)] = INV4;

    long long e = m - 1;
    while (e > 0) {
        if (e & 1LL) cur = multiplyVector(cur, trans, n);
        trans = multiplyMatrix(trans, trans, n);
        e >>= 1LL;
    }

    auto [lastGo, lastGood] = buildTransfer(n, true);
    ll prob = cur[S];
    for (int i = 0; i < S; i++) {
        prob = (prob + cur[i] * lastGood[i]) % MOD;
    }

    long long vertices = 1LL * (n + 1) * (m + 1);
    return prob * modPow(4, vertices) % MOD;
}

int main() {
    setIO();

    int t;
    cin >> t;
    while (t--) {
        int n;
        long long m;
        cin >> n >> m;
        cout << solveCase(n, m) << '\n';
    }

    return 0;
}