#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
int n, m;

ll mod_mul(ll a, ll b, ll n) {
    a %= n;  //优化后只要在开头模一次，其他的地方用if，效率提升近一倍
    b %= n;
    ll res = 0;
    while (b) {
        if (b & 1) {
            res += a;
            if (res > n) res -= n;
        }
        a += a;
        if (a > n) a -= n;
        b /= 2;  //没开o2的话要换成b>>=1
    }
    return res;
}

ll mod_exp(ll a, ll b, ll n) {
    ll res = 1;
    a = a % n;
    while (b) {
        if (b & 1) res = mod_mul(res, a, n);
        a = mod_mul(a, a, n);
        b /= 2;
    }
    return res;
}

ll dat[9][9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 15, 339, 4761, 52929, 517761, 4767849, 43046721, 387420489,
0, 339, 16485, 518265, 14321907, 387406809, 460338013, 429534507, 597431612,
0, 4761, 518265, 43022385, 486780060, 429534507, 792294829, 175880701, 246336683,
0, 52929, 14321907, 486780060, 288599194, 130653412, 748778899, 953271190, 644897553,
0, 517761, 387406809, 429534507, 130653412, 246336683, 579440654, 412233812, 518446848,
0, 4767849, 460338013, 792294829, 748778899, 579440654, 236701429, 666021604, 589237756,
0, 43046721, 429534507, 175880701, 953271190, 412233812, 666021604, 767713261, 966670169,
0, 387420489, 597431612, 246336683, 644897553, 518446848, 589237756, 966670169, 968803245 };

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        if (n == 1 || m == 1) {
            printf("0\n");
        }
        else if (n <= 9 || m <= 9) {
            n--;
            m--;
            printf("%lld\n", dat[n][m] % MOD);
        }
        else {
            printf("%lld\n", mod_exp(3, 1LL * n * m, MOD));
        }
    }
    return 0;
}