#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 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 cnt=0;
int a[10][10];
int b[10][10];
int ans=0;
bool ck(int cnt){

    for(int i=1;i<=n-1;i++){

        for(int j=1;j<cnt;j++){

            for(int k=i+1;k<=n;k++){
                // cout << a[i][j] << " " << a[i][cnt] << " " << a[k][j] << " " << a[k][cnt] << "\n";
                if(a[i][j]==a[i][cnt]&&a[k][j]==a[k][cnt]||a[i][j]==a[k][j]&&a[i][cnt]==a[k][cnt]) {
                    // cout<<"Hello\n";
                    
                    return 0;
                }
            }
        }
    }
    return 1;
}
void fu(){

    for(int i=1;i<=n;i++){

        for(int j=1;j<=cnt;j++){

            b[i][j]=a[i][j];
        }
    }
}
void dfs(int d,int num){

    if(d>m) {

        ans++;
        return;
    }

    if(num==n){

        for(int i=1;i<=3;i++){

            a[num][d]=i;
            if(ck(d)) dfs(d+1,1);
        }
    } else {

        for(int i=1;i<=3;i++){

            a[num][d]=i;
            dfs(d,num+1);
        }
    }
}
void solve()
{
    // cin>>n>>m;
    cin>>n>>m;
    ans=0;
    int res = qpow(3, n * m);
    // for(int i=1;i<=2;i++){

    //     for(int j=1;j<=2;j++){

    //         a[i][j]=1;
    //     }
    // }
    // cout << ck(2);
    // return;
    if(n>=8||m>=8){

        cout<<res<<"\n";
    } else {
        dfs(1, 1);
        res-=ans;
        M(res);
        // cout<<ans<<"\n";
        cout<<res<<"\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;
    while (t--)
    {

        solve();
    }
}