#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int LL
const int N = 2e3 + 5;
const int MOD = 1e9 + 7;

int ksm(int a, int b, int c)
{
    int ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % c;
        b >>= 1;
        a = a * a % c;
    }
    return ans;
}
int a[15][15];
int lx, ly;
int dfs(int x, int y)
{
    int ans = 0;
    for (int i = 1; i <= 3; i++) {
        a[x][y] = i;
        int f = 1;
        for (int j = x - 1; j >= 1; j--) {
            for (int z = y - 1; z >= 1 && f; z--) {
                if (a[x][y] == a[j][y] && a[x][z] == a[j][z]) f = 0;
                if (a[x][y] == a[x][z] && a[j][y] == a[j][z]) f = 0;
            }
            if (!f) break;
        }
        if (f) {
            if (x == lx && y == ly) ans++;
            else if (x == lx)
                ans += dfs(1, y + 1);
            else
                ans += dfs(x + 1, y);
        }
    }
    return ans;
}
int res[9][9] =
    {3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 9, 66, 390, 1800, 6120, 13680, 15120, 0, 0, 27, 390, 3198, 13176, 27000,
     13680, 15120, 0, 0, 81, 1800, 13176, 24336, 4320, 0, 0, 0, 0, 243, 6120, 27000, 4320, 4320, 0, 0, 0, 0, 729, 13680,
     13680, 0, 0, 0, 0, 0, 0, 2187, 15120, 15120, 0, 0, 0, 0, 0, 0, 6561, 0, 0, 0, 0, 0, 0, 0, 0, 19683, 0, 0, 0, 0, 0,
     0, 0, 0};
void init()
{
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            memset(a, 0, sizeof a);
            lx = i, ly = j;
            res[i][j] = dfs(1, 1);
        }
    }
}
void solve()
{
    int n, m;
    cin >> n >> m;
    if (n == 1 || m == 1) {
        cout << "0\n";
        return;
    }
    if (n <= 9 && m <= 9) {
        cout << (ksm(3, n * m, MOD) - res[n - 1][m - 1] + MOD) % MOD << "\n";
    }
    else
        cout << ksm(3, n * m, MOD) << "\n";
}
signed main()
{
//    init();
    ios::sync_with_stdio(false), cin.tie(0);
    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}