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

# ifndef ONLINE_JUDGE
# include "debug.h"
# else
# define debug(...) 0721
# define ps 0721
# endif

using i32 = signed;
using i64 = long long;

const int mod = 1e9 + 7;

int power(int a,int n) {
    int res = 1;
    while(n) {
        if(n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
map<pair<int,int>,int> mp;
vector<int> res = {
15,339,4761,52929,517761,4767849,43046721,339,16485,518265,14321907,387406809,870403484,961694959,4761,518265,43022385,191812792,961694959,796636458,498665608,52929,14321907,191812792,180047804,989859015,348873122,689956897,517761,387406809,961694959,989859015,46619359,914644770,911671240,4767849,870403484,796636458,348873122,914644770,735013706,918707425,43046721,961694959,498665608,689956897,911671240,918707425,38349043
};

void solve() {
    int n,m;
    cin >> n >> m;

    vector<vector<int>> a(n + 1,vector<int>(m + 1, 0));
    vector<vector<int>> b(n + 1,vector<int>(4,0));
    auto check = [&] (int x,int y,int val) -> bool {
        a[x][y] = val;
        if(b[x][0] <=3  && b[x][1] <= 3 && b[x][2] <= 3) {
            for (int i = 1; i < x; i++) {
                for (int j = 1; j < y; j++) {
                    
                    if(a[i][j] == a[i][y] && a[x][y] == a[x][j]) {
                        return false;
                    }
                    if(a[i][j] == a[x][j] && a[i][y] == a[x][y]) {
                        return false;
                    }
                } 
            }
            return true;
        }

        return false;
    };
    int ans = 0;

    auto dfs = [&] (auto self,int x,int y) -> void {
        if(x > n) {
            ans++;
            return;
        }
        if(y > m) {
            self(self,x + 1,1);
            return;
        }
        for (int i = 1; i <=3 ; i++) {
            b[x][i]++;
            if(check(x,y,i)) {
                self(self,x,y + 1);
            }
            b[x][i]--;
        }
    };
    if(n == 1 || m == 1) {
        cout << 0 << '\n';
        return;
    }
    if(n > 8 || m > 8) {
        cout << power(3,n * m) << '\n';
    }
    cout << res[mp[{n,m}] - 1] << '\n';
}

i32 main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

# ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
    freopen("Error.txt", "w", stderr);
# endif

    int tot = 0;
    for (int i = 2; i <= 8;i++) {
        for (int j = 2;j <= 8;j++) {
            mp[{i,j}] = ++tot;
        }
    }
    i32 t = 1;
    cin >> t;
    while (t --) {
        solve();
    }
    return 0;
}