#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
#define ld long double
#define M(x)          \
    {                 \
        x %= mod;     \
        if (x < 0)    \
            x += mod; \
    }
#define error           \
    {                   \
        cout << "No\n"; \
        return;         \
    }
#define all(x) (x.begin(), x.end())
template <typename A, typename B>
bool smax(A &a, const B &b) { return a < b ? a = b, 1 : 0; }
template <typename A, typename B>
bool smin(A &a, const B &b) { return b < a ? a = b, 1 : 0; }

const int N = 1e6 + 10;
int a[N];
int n, m, k;
const int inf = 1e18;

ld eps = 1e-9;
bool eql(ld x, ld y) { return fabs(x - y) < eps; }
bool lt(ld x, ld y) { return !eql(x, y) && x < y; }
bool rt(ld x, ld y) { return !eql(x, y) && x > y; }
int mod = 1e9 + 7;
int qpow(int x, int p)
{

    int res = 1;
    while (p)
    {

        if (p & 1)
            res = res * x % mod;
        p >>= 1;
        x = x * x % mod;
    }
    return res;
}
int ans[10][10];
void solve()
{
    
    if (n > m)
        swap(n, m);
    int res=qpow(3,n*m);

    if(n==1||m==1){

        cout<<0<<"\n";
        return;
    }
    if(n>=8||m>=8){

        cout<<res<<"\n";
    } else {
        
        cout<<ans[n][m]<<"\n";
    }
}
signed main()
{
    // freopen("D://Desktop//VSCODE//input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    ans[1][1]=0      ;
    ans[1][2]=0      ;
    ans[1][3]=0      ;
    ans[1][4]=0      ;
    ans[1][5]=0      ;
    ans[1][6]=0      ;
    ans[1][7]=0      ;
    ans[2][2]=15     ;
    ans[2][3]=339    ;
    ans[2][4]=4761   ;
    ans[2][5]=52929  ;
    ans[2][6]=517761 ;
    ans[2][7]=4767849;
    ans[3][3]=16485  ;
    ans[3][5]=14321907;
    ans[3][6]=387406809;
    ans[3][7]=460338013;
    ans[4][4]=43022385;
    ans[4][5]=486780060;
    ans[4][6]=429534507;
    ans[4][7]=792294829;
    ans[5][5]=288599194;
    ans[5][6]=130653412;
    ans[5][7]=748778899;
    ans[6][6]=246336683;
    ans[6][7]=579440654;
    ans[7][7]=236701429;
    int t1=t;
    while (t--)
    {
        cin >> n >> m;
        if(t1-t==204) {

            cout<<n<<"*"<<m<<"\n";
        }
        solve();
    }
}