#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
const ll mod=1e9+7;
int g[10][10];
int n,m;
ll ans;

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

void dfs(int x,int y)
{
    if (x == n + 1) return ;
    for(int k=1;k<=3;++k)
    {
        g[x][y]=k;
        int flag=0;
        for(int i=1;i<x;++i)
        {
            for(int j=1;j<y;++j)
            {
                if((g[x][y]==g[x][j]&&g[i][j]==g[i][y])||(g[i][j]==g[x][j]&&g[i][y]==g[x][y]))
                {
                    int cnt=m*n-(x-1)*m-y;
                    ans=(ans+qmi(3,cnt))%mod;
                    flag=1;break;
                }
            }
            if(flag)break;
        }
        if(flag)continue;
        int xx,yy;
        if(y==m){xx=x+1;yy=1;}
        else {xx=x;yy=y+1;}
        
        dfs(xx,yy);
    }
}
std::map<std::pair<int, int>, int> mp;
int a[10][10] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
    {0, 0,0,0,0,0,0,0,0,0},
    {0, 0,15,339,4761,52929,517761,4767849,43046721,387420489},
    {0, 0,339,16485,518265,14321907,387406809,460338013,429534507,597431612},
    {0, 0,4761,518265,43022385,486780060,429534507,792294829,175880701,246336683},
    {0, 0,52929,14321907,486780060,288599194,130653412,748778899,953271190,644897553},
    {0, 0,517761,387406809,429534507,130653412,246336683,579440654,412233812,518446848},
    {0, 0,4767849,460338013,792294829,748778899,579440654,236701429,666021604,589237756},
    {0, 0,43046721,429534507,175880701,953271190,412233812,666021604,767713261,966670169},
    {0, 0,387420489,597431612,246336683,644897553,518446848,589237756,966670169,968803245}
};
signed main()
{
    // for (int i = 1; i <= 9; i ++) {
    //     for (int j = 1; j <= 9; j ++) {
    //         n = i, m = j;
    //         ans = 0;
    //         dfs(1, 1);
    //         std::cout << ans << ',';
    //     }
    //     std::cout << '\n';
    // }
    int t;
    std::cin >> t;
    while (t --) {
        int nn, mm;
        std::cin >> nn >> mm;
        if (std::max(nn, mm) > 9) {
            std::cout << qmi(3, nn * mm) << '\n';
        } else {
            std::cout << a[nn][mm] << '\n';
        }
    }
    return 0;
}