palid

#include <iostream>
#define NMax 1000
#define Kmax 10
#define MOD 1000000007
#define BAZA 10000
using namespace std;
int c[2][Kmax];
typedef int Huge[NMax+3];

int PUTERE(int a,int b)
{
    if(b==0)
        return 1;
    else
        if(b%2==0)
            return PUTERE((a*a)%MOD,b/2);
        else
            return a*PUTERE((a*a)%MOD,b/2)%MOD;
}

void Atrib0(Huge H) /// H <- 0
{
    H[0]=0;
}

void AtribValue(Huge H,unsigned long X) /// H <- X
{
    H[0]=0;
    while(X)
        ++H[0],H[H[0]]=X%BAZA,X/=BAZA;
}

void Add(Huge A,Huge B) /// A <- A+B
{
    int i,T=0;
    if(B[0]>A[0])
    {
        for(i=A[0]+1;i<=B[0];)
            A[i++]=0;
        A[0]=B[0];
    }
    else
        for(i=B[0]+1;i<=A[0];)
            B[i++]=0;
    for(i=1;i<=A[0];++i)
        A[i]+=B[i]+T,T=A[i]/BAZA,A[i]%=BAZA;
    if(T)
        A[++A[0]]=T;
}

void Subtract(Huge A,Huge B) /// A <- A-B
{
    int i,T=0;
    for(i=B[0]+1;i<=A[0];)
        B[i++]=0;
    for(i=1;i<=A[0];++i)
        A[i]+=(T=(A[i]-=B[i]+T)<0)?BAZA:0;
    /* Adica A[i]=A[i]-(B[i]+T);
       if (A[i]<0) T=1; else T=0;
       if (T) A[i]+=BAZA; */
    while(!A[A[0]])
        A[0]--;
}

void Mult(Huge H,unsigned long X) /// H <- H*X
{
    int i;
    unsigned long T=0;
    for(i=1;i<=H[0];++i)
        H[i]=H[i]*X+T,T=H[i]/BAZA,H[i]=H[i]%BAZA;
    while(T) /// Cat timp exista transport
        H[++H[0]]=T%BAZA,T/=BAZA;
}

void MultHuge(Huge A,Huge B) /// A <- A x B
{
    int i,j,T=0;
    Huge C;
    C[0]=A[0]+B[0]-1;
    for(i=1;i<=A[0]+B[0];)
        C[i++]=0;
    for(i=1;i<=A[0];++i)
        for(j=1;j<=B[0];++j)
            C[i+j-1]+=A[i]*B[j];
    for(i=1;i<=C[0];++i)
        T=(C[i]+=T)/BAZA,C[i]%=BAZA;
    if(T)
        C[++C[0]]=T;
    for(int i=0;i<=C[0];++i)
        A[i]=C[i];
}

unsigned long Divide(Huge A, unsigned long X) /// A <- A/X si intoarce A%X
{
    int i;
    unsigned long R=0;
    for(i=A[0];i;--i)
        A[i]=(R=BAZA*R+A[i])/X,R%=X;
    while(!A[A[0]] && A[0]>1)
        A[0]--;
    return R;
}

unsigned long Mod(Huge A,unsigned long X) /// Intoarce A%X (restul)
{
    int i;
    unsigned long R=0;
    for(i=A[0];i;--i)
        R=(BAZA*R+A[i])%X;
    return R;
}

void Afisare(Huge H)
{

    for(int i=H[0];i>0;--i)
        cout<<H[i];
    cout<<'\n';
}

void pdcomb(int n) /// folosesc doar doua linii (0 si 1)
{
    for(int i=0;i<=Kmax;++i)
        c[0][i]=c[1][i]=0;
    c[0][0]=c[1][0]=1; /// coloana 0
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=i;++j)
            c[1][j]=(c[0][j]+c[0][j-1]);
        for(int k=0;k<=i;++k)
            c[0][k]=c[1][k];
    }
}

void P(Huge A,int n) /// A <- A^n logaritmic
{
    Huge P;P[0]=1,P[1]=1;
    if(n==0)
        A[0]=1,A[1]=1;
    else
        while(n>0)
        {
            if(n%2==1)
                MultHuge(P,A);
            n/=2;
            MultHuge(A,A);
        }
    for(int i=0;i<=P[0];++i)
        A[i]=P[i];
}

int main()
{
    int n,m,k;
    Huge SOL,A;
    cin>>n;
    pdcomb(n);
    while(n--)
    {
        cin>>m>>k;
        if(m%2)
            ++m;
        if(k==1)
            cout<<1<<'\n';
        else
            if(k==2)
                cout<<PUTERE(2,m-1)%MOD<<'\n';
            else
            {
                Atrib0(SOL);
                pdcomb(k);
                for(int i=0;k>=2*i;++i)
                {
                    AtribValue(A,k-2*i);
                    P(A,m);
                    Mult(A,c[1][i]);
                    Add(SOL,A);
                }
                Divide(SOL,PUTERE(2,k-1));
                cout<<Mod(SOL,MOD)<<'\n';
            }
    }
    return 0;
}