#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define debug(x) cout<<#x<<": "<<x<<endl
typedef pair<ll,ll> PLL;
#define ld long double
const ll mod=1e9+7;

ll f[10][10]={1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,0,15,339,4761,52929,517761,4767849,43046721,387420489,1,0,339,16485,518265,14321907,387406809,460338013,429534507,597431612,1,0,4761,518265,43022385,486780060,429534507,792294829,175880701,246336683,1,0,52929,14321907,486780060,288599194,130653412,748778899,953271190,644897553,1,0,517761,387406809,429534507,130653412,246336683,579440654,412233812,518446848,1,0,4767849,460338013,792294829,748778899,579440654,236701429,666021604,589237756,1,0,43046721,429534507,175880701,953271190,412233812,666021604,767713261,966670169,1,0,387420489,597431612,246336683,644897553,518446848,589237756,966670169,968803245};
int a[10][10];

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

void solve()
{
	ll n,m;
	cin>>n>>m;
	if(max(n,m)>9)
	{
		cout<<qpow(3,n*m)<<endl;
	}
	else
	{
		cout<<f[n][m]<<endl;
	}
}

int main()
{

	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	int T=1;
	cin>>T;

	while(T--)
	{
		solve();
	}
	return 0;
}