#include <bits/stdc++.h>

using namespace std;

const int P = 1e9 + 7;

int ksm(int y)
{
    int x = 3, res = 1;
    while (y) {
        if (y & 1) {
            res = 1ll * res * x % P;
        }
        x = 1ll * x * x % P;
        y >>= 1;
    }
    return res;
}

int n, m, a[25][25], res;

void dfs(int x, int y)
{
    if (x > n) {
        int chk = 0;
        for (int i = 1; i <= n && !chk; ++i) {
            for (int j = i + 1; j <= n && !chk; ++j) {
                for (int k = 1; k <= m; ++k) {
                    for (int l = k + 1; l <= m; ++l) {
                        chk |= ((a[i][k] == a[i][l]) && (a[j][k] == a[j][l]));
                        chk |= ((a[i][k] == a[j][k]) && (a[i][l] == a[j][l]));
                    }
                }
            }
        }
        res += chk;
        return;
    }
    for (int i = 0; i < 3; ++i) {
        a[x][y] = i;
        if (y == m) {
            dfs(x + 1, 1);
        } else {
            dfs(x, y + 1);
        }
    }
    return;
}

signed main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        if (n > m) {
            swap(n, m);
        }
        if (n == 1) {
            puts("0");
            continue;
        }
        if (m >= 8) {
            printf("%d\n", ksm(n * m));
            continue;
        }
        if (n == 2 && m == 7) {
            puts("4767849");
            continue;
        }
        if (n >= 3 && m >= 5) {
            printf("%d\n", ksm(n * m));
            continue;
        }
        if (n == 4 && m == 4) {
            puts("43022385");
            continue;
        }
        res = 0;
        dfs(1, 1);
        printf("%d\n", res);
    }
    return 0;
}