#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,
    339,       16485,     518265,  14321907,  387406809, 460338013,
    429534507, 597431612, 4761,    518265,    43022385,  486780060,
    429534507, 792294829, 52929,   14321907,  486780060, 288599194,
    130653412, 748778899, 517761,  387406809, 429534507, 130653412,
    246336683, 579440654, 4767849, 460338013, 792294829, 748778899,
};
void solve() {
    int n, m;
    cin >> n >> m;

    if (n == 1 || m == 1) {
        cout << 0 << '\n';
        return;
    }
    if (n > 7 || m > 7) {
        cout << power(3, n * m) << '\n';
        return;
    }
    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 <= 7; i++) {
        for (int j = 2; j <= 7; j++) {
            mp[{i, j}] = tot++;
        }
    }
    cin >> t;
    while (t--)
        solve();
    return 0;
}