/*
 * Copyright© 2024 Heratino & Nelofus. All rights reserved.
 * author: Heratino & Nelofus
 * Problem: 
 * Tag: 
 * Memory Limit: 
 * Time Limit: 
 * Source: 
 */

// Narcissus & どうか安寧な記憶を

#include <bits/stdc++.h>
using i64 = long long;

//{{{星光闪耀
template<typename Ta, typename Tb>
inline void chkmax(Ta &a, const Tb &b) {if (a < b)	a = b;}
template<typename Ta, typename Tb>
inline void chkmin(Ta &a, const Tb &b) {if (a > b)	a = b;}
//}}}

constexpr int N = 10;
constexpr int mod = 1e9 + 7;

inline i64 f_pow(i64 a, int k) {
	i64 base = 1;
	for (; k; k >>= 1, a = 1ll * a * a % mod)
		if (k & 1)
			base = base * a % mod;
	return base;
}

inline int Minu(const int &x, const int &y) {
	return x - y < 0 ? x - y + mod : x - y;
}
inline int Plus(const int &x, const int &y) {
	return x - y >= mod ? x + y - mod : x + y;
}

int col[N][N];
int counter = 0;
void dfs(int x, int y, int mx, int my) {
	for (int k = 0; k < 3; k++) {
		col[x][y] = k;
		bool flag = true;
		for (int i = 1; i < x; i++) {
			for (int j = 1; j < y; j++) {
				if (col[i][j] == col[i][y] && col[x][j] == col[x][y]) {
					flag = false;
				}
				if (col[i][j] == col[x][j] && col[i][y] == col[x][y]) {
					flag = false;
				}
				if (!flag)
					break;
			}
			if (!flag)
				break;
		}
		if (flag)  {
			if (y == my) {
				if (x == mx) {
					counter++;
				} else {
					dfs(x + 1, 1, mx, my);
				}
			} else {
				dfs(x, y + 1, mx, my);
			}
		}
	}
}

int solve(int n, int m) {
	counter = 0;
	dfs(1, 1, n, m);
	return Minu(f_pow(3, n * m), counter);
	//	return counter;
}
int answer[N][N] = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 15, 339, 4761, 52929, 517761, 4767849, 43046721, 387420489, 486784380}, {0, 339, 16485, 518265, 14321907, 387406809, 460338013, 429534507, 597431612, 130653412}, {0, 4761, 518265, 43022385, 486780060, 429534507, 792294829, 175880701, 246336683, 953271190}, {0, 52929, 14321907, 486780060, 288599194, 130653412, 748778899, 953271190, 644897553, 710104287}, {0, 517761, 387406809, 429534507, 130653412, 246336683, 579440654, 412233812, 518446848, 947749553}, {0, 4767849, 460338013, 792294829, 748778899, 579440654, 236701429, 666021604, 589237756, 662963356}, {0, 43046721, 429534507, 175880701, 953271190, 412233812, 666021604, 767713261, 966670169, 322934415}, {0, 387420489, 597431612, 246336683, 644897553, 518446848, 589237756, 966670169, 968803245, 954137859}, {0, 486784380, 130653412, 953271190, 710104287, 947749553, 662963356, 322934415, 954137859, 886041711}};

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int T;
	std::cin >> T;
	while (T--) {
		int n, m;
		std::cin >> n >> m;
		if (n == 1 || m == 1) {
			std::cout << "0" << '\n';
		} else if (n <= 10 && m <= 10) {
			std::cout << answer[n - 1][m - 1] << '\n';
		} else {
			std::cout << f_pow(3, n * m) << '\n';
		}
	}
	return 0;
}