#include <bits/stdc++.h>

/* Orther */
#define int long long
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
using namespace std;

/* Pair */
#define x first
#define y second

/* Data type */
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using VI = vector<int>;

/* STL */
#define eb emplace_back
#define ef emplace_front
#define pb push_back
#define pf push_front
#define mp make_pair
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define all1(x) x.begin()+1,x.end()

/* Random */
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define random(a,b) rng()%(b-a+1)+a

/* Contest */
const int INF = 0x3f3f3f3f ; // 1e9
const int MOD =  1e9 + 7 ;
const int N = 2e5 + 10, M = 55;

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

int sbscw[9][9]=
{ 
	{0,0,0,0,0,0,0,0,0},
	{0,15,339,4761,52929,517761,4767849,43046721,387420489},
	{0,339,16485,518265,14321907,387406809,460338013,429534507,597431612},
	{0,4761,518265,43022385,486780060,429534507,792294829,175880701,246336683},
	{0,52929,14321907,486780060,288599194,130653412,748778899,953271190,644897553},
	{0,517761,387406809,429534507,130653412,246336683,579440654,412233812,518446848},
	{0,4767849,460338013,792294829,748778899,579440654,236701429,666021604,589237756},
	{0,43046721,429534507,175880701,953271190,412233812,666021604,767713261,966670169},
	{0,387420489,597431612,246336683,644897553,518446848,589237756,966670169,968803245}
};
void Rainbow_()
{
    int n , m ;
    cin >> n >> m;
    
    if (n == 1 || m == 1 ) {
    	cout << 0 << '\n';
    } else if ( max( n , m ) > 9 ) {
    	cout << qpow(3 ,n * m);
    } else {
    	n -- , m -- ;
    	cout << sbscw[n][m]<<'\n';
    }
}
 
signed main()
{   
    IOS;
    int _ = 1;
    cin >> _;
 
    while ( _ -- ) 
        Rainbow_();
 
    return 0;
}