#include<bits/stdc++.h>
using namespace std;

#define ll long long
const ll mod=1e9+7;
int g[8][8];
int n,m;
ll ans;

ll qmi(ll a,ll b)
{
    ll res=1ll;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

void dfs(int x,int y)
{
    if (x == n + 1) return ;
    for(int k=1;k<=3;++k)
    {
        g[x][y]=k;
        int flag=0;
        for(int i=1;i<x;++i)
        {
            for(int j=1;j<y;++j)
            {
                if((g[x][y]==g[x][j]&&g[i][j]==g[i][y])||(g[i][j]==g[x][j]&&g[i][y]==g[x][y]))
                {
                    int cnt=m*n-(x-1)*m-y;
                    ans=(ans+qmi(3,cnt))%mod;
                    flag=1;break;
                }
            }
            if(flag)break;
        }
        if(flag)continue;
        int xx,yy;
        if(y==m){xx=x+1;yy=1;}
        else {xx=x;yy=y+1;}
        
        dfs(xx,yy);
    }
}
std::map<std::pair<int, int>, int> mp;
int main()
{
    for (int i = 1; i <= 7; i ++) {
        for (int j = 1; j <= 7; j ++) {
            n = i, m = j;
            ans = 0;dfs(1, 1);
            mp[{i, j}] = ans;
        }
    }
    int t;
    std::cin >> t;
    while (t --) {
    int n, m;
    std::cin >> n >> m;
    if (std::max(n, m) > 7) {
        std::cout << qmi(3, n * m) << '\n';
    } else {
        std::cout << mp[{n, m}] << '\n';
    }
    }
    return 0;
}