#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=4e6+10;
const int mod=1e9+7;

int nums[8][8];

int pow3[N];

void solve()
{
    int n,m;
    cin >> n >> m;
    if(n<m) swap(n,m);
    if(n>7)
    {
        ll ans=pow3[n*m];
        cout << ans << "\n";
        return;
    }
    if(m==1)
    {
        cout << "0\n";
        return;
    }
    ll ans=pow3[n*m]-nums[n][m];
    ans%=mod;
    ans=(ans+mod)%mod;
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    pow3[0]=1;
    for(int i=1;i<N;i++) pow3[i]=(ll)pow3[i-1]*3%mod;

    nums[2][1]=9;
    nums[2][2]=66;

    nums[3][1]=27;
    nums[3][2]=390;
    nums[3][3]=3198;

    nums[4][1]=81;
    nums[4][2]=1800;
    nums[4][3]=13176;
    nums[4][4]=24336;

    nums[5][1]=243;
    nums[5][2]=6120;
    nums[5][3]=27000;
    nums[5][4]=4320;
    nums[5][5]=4320;

    nums[6][1]=729;
    nums[6][2]=13680;
    nums[6][3]=13680;

    nums[7][1]=2187;
    nums[7][2]=15120;
    nums[7][3]=15120;
    int T;
    cin >> T;
    while(T--) solve();
    return 0;

}