palid

#include <iostream>
#define MOD 1000000007
using namespace std;

int n, m, k;
unsigned long long p2, sol, pk, c[10][10], pt, pl, pp;
int mod(int a, int md)
{
    return (a%md + md) % md;
}

unsigned long long power(unsigned int x, unsigned long long y, int p)   /// (x^y)%MOD
{
    unsigned long long res = 1;
    x = x % p;
    while(y > 0)
    {
        if(y & 1)
            res =1ULL*(res*x) % p;
        y = y>>1;
        x = (1ULL*x*x) % p;
    }
    return res;
}


int main()
{
    int i, j, t;
    cin>>n;

    for(i=1;i<=n;i++)
    {
        cin>>m>>k;
        if(m%2 && m>2)  /// daca m este impar il fac m+1
            m++;
        if(k==1)
            cout<<1<<'\n';
        else if(m==1 || m==2)
            cout<<k<<'\n';
        else if(k==2)
        {
            p2=1ULL*power(2,(m-1), MOD); /// 2^m-1
            cout<<p2<<'\n';
        }
        else if(k==3)
        {
            p2=(power(3,m,MOD)+(3%MOD))%MOD;  /// 3^m+3
            sol=mod(p2/4,MOD);  /// (3^m+3)/4;
            cout<<sol<<'\n';
        }
        else if(k==4)  /// se calculeza (4^m+4*2^m+6)/8
        {
            p2=8;
            pk=power(4,m,MOD);
            sol=pk;
            pk=power(2,m+2,MOD);
            sol=mod(sol+pk+6,MOD);
            sol=mod(sol/p2,MOD);
            cout<<sol<<'\n';
        }
        else if(k==5)  /// se calculeza (5^m+5*3^m+10)/16
        {
            p2=16;
            pk=power(5,m,MOD);
            sol=pk;
            pk=power(3,m,MOD);
            pk=mod(pk*5,MOD);
            sol=mod(sol+pk+10,MOD);
            sol=mod(sol/p2,MOD);
            cout<<sol<<'\n';
        }
        else if(k==6)   /// se calculeaza (6^m+6*4^m+15*2^m+20)/32
        {
            p2=32;
            pk=power(6,m,MOD);
            pt=power(4,m,MOD);
            pt=mod(pt*6,MOD);
            pl=power(2,m,MOD);
            pl=mod(pl*15,MOD);
            sol=mod(pk+pt+pl+20,MOD);
            sol=mod(sol/p2,MOD);
            cout<<sol<<'\n';
        }
        else if(k==7)   /// se calculeaza (7^m+7*5^m+21*3^m+35)/64
        {
            p2=64;
            pk=power(7,m,MOD);
            pt=power(5,m,MOD);
            pt=mod(pt*7,MOD);
            pl=power(3,m,MOD);
            pl=mod(pl*21,MOD);
            sol=mod(pk+pt+pl+35,MOD);
            sol=mod(sol/p2,MOD);
            cout<<sol<<'\n';
        }
        else if(k==8)  /// se calculeaza (8^m+8*6^m+28*4^m+56*2^m+70)/128
        {
            p2=128;
            pk=power(8,m,MOD);
            pt=power(6,m,MOD);
            pt=mod(pt*8,MOD);
            pl=power(4,m,MOD);
            pl=mod(pl*28,MOD);
            pp=power(2,m,MOD);
            pp=mod(pp*56,MOD);
            sol=mod(pk+pt+pl+pp+70, MOD);
            sol=mod(sol/p2,MOD);
            cout<<sol<<'\n';
        }
        else
        {
            p2=256;
            c[1][0]=1;
            c[1][1]=1;
            for(i=2; i<=9; i++)  /// calcul combinari de k luate cate j
            {
                c[i][0]=1;
                c[i][i]=1;
                for(j=1; j<i; j++)
                    c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
            }
            j=0;
            t=0;
            while(k-t>=0)
            {
                pk=1ULL*power((k-t),m,MOD);
                sol=1ULL*(sol+c[k][j]*pk)%MOD;
                j++;t+=2;
            }
            sol=mod(sol/p2,MOD);
            cout<<sol<<'\n';
        }
    }
    return 0;
}