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

#ifdef LOCAL
#include "C:\Program Files\DEBUG\debug.h"
#else
#define debug(...) 114514
#define ps 114514
#endif

const int mod = 1e9 + 7;

int power(int a, int n) {
    int res = 1;
    while (n) {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

map<pair<int, int>, int> mp;
vector<int> res = {
    15,       339,       4761,      52929,     517761,    4767849,   43046721,
    339,      16485,     518265,    14321907,  387406809, 460338013, 429534507,
    4761,     518265,    43022385,  486780060, 429534507, 792294829, 175880701,
    52929,    14321907,  486780060, 288599194, 130653412, 748778899, 953271190,
    517761,   387406809, 429534507, 130653412, 246336683, 579440654, 412233812,
    4767849,  460338013, 792294829, 748778899, 579440654, 236701429, 666021604,
    43046721, 429534507, 175880701, 953271190, 412233812, 666021604, 767713261};
void solve() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> a(n + 1, vector<int>(m + 1, 0));
    vector<vector<int>> b(n + 1, vector<int>(4, 0));
    auto check = [&](int x, int y, int val) -> bool {
        a[x][y] = val;
        if (b[x][0] <= 3 && b[x][1] <= 3 && b[x][2] <= 3) {
            for (int i = 1; i < x; i++) {
                for (int j = 1; j < y; j++) {
                    if (a[i][j] == a[i][y] && a[x][y] == a[x][j]) {
                        return false;
                    }
                    if (a[i][j] == a[x][j] && a[i][y] == a[x][y]) {
                        return false;
                    }
                }
            }
            return true;
        }

        return false;
    };
    int ans = 0;

    auto dfs = [&](auto self, int x, int y) -> void {
        if (x > n) {
            ans++;
            return;
        }
        if (y > m) {
            self(self, x + 1, 1);
            return;
        }
        for (int i = 1; i <= 3; i++) {
            b[x][i]++;
            if (check(x, y, i)) {
                self(self, x, y + 1);
            }
            b[x][i]--;
        }
    };
    if (n == 1 || m == 1) {
        cout << 0 << '\n';
        return;
    }
    if (n > 8 || m > 8) {
        cout << power(3, n * m) << '\n';
    }
    cout << res[mp[{n, m}]] << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
    int tot = 0;
    for (int i = 2; i <= 8; i++) {
        for (int j = 2; j <= 8; j++) {
            mp[{i, j}] = tot++;
        }
    }
    cin >> t;
    while (t--)
        solve();
    return 0;
}