#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int n,m;

ll mod_mul(ll a, ll b, ll n) {
  a %= n;  //优化后只要在开头模一次，其他的地方用if，效率提升近一倍
  b %= n;
  ll res = 0;
  while (b) {
    if (b & 1) {
      res += a;
      if (res > n) res -= n;
    }
    a += a;
    if (a > n) a -= n;
    b /= 2;  //没开o2的话要换成b>>=1
  }
  return res;
}

ll mod_exp(ll a, ll b, ll n) {
  ll res = 1;
  a = a % n;
  while (b) {
    if (b & 1) res = mod_mul(res, a, n);
    a = mod_mul(a, a, n);
    b /= 2;
  }
  return res;
}

ll dat[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};

int main() {
  int T;
  scanf("%d",&T);
  while(T--){
    scanf("%d%d",&n,&m);
    if(n==1||m==1){
      printf("0\n");
    }
    else if(n<=9||m<=9){
      n--;
      m--;
      printf("%lld\n",dat[n][m]%MOD);
    }
    else{
      printf("%lld\n",mod_exp(3,1LL*n*m,MOD));
    }
  }
  return 0;
}