#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const ll Mod=1e9+7;

const int msize=2;

const int N=4;

struct Mat

{

    ll mat[N][N];

};

Mat operator *(Mat a, Mat b)

{

    Mat c;

    memset(c.mat, 0, sizeof(c.mat));

    for(int k = 0; k < msize; ++k)

        for(int i = 0; i < msize; ++i)

            if(a.mat[i][k])

                for(int j = 0; j < msize; ++j)

                    if(b.mat[k][j])

                        c.mat[i][j] = (c.mat[i][j] +a.mat[i][k] * b.mat[k][j])%Mod;

    return c;

}

Mat operator ^(Mat a, ll k)

{

    Mat c;

    memset(c.mat,0,sizeof(c.mat));

    for(int i = 0; i < msize; ++i)

        c.mat[i][i]=1;

    for(; k; k >>= 1)

    {

        if(k&1) c = c*a;

        a = a*a;

    }

    return c;

}

Mat operator -(Mat a,Mat b)

{

    for(int i=0; i<msize; i++)

        for(int j=0; j<msize; j++)

            a.mat[i][j]=(a.mat[i][j]-b.mat[i][j])%Mod;

    return a;

}

int main()

{

//    freopen("in.txt","r",stdin);

    int t;

    ll n,m;

    Mat A,B1,B2;

    A.mat[0][0]=1,A.mat[0][1]=2;

    A.mat[1][0]=1,A.mat[1][1]=0;

    B1.mat[0][0]=B1.mat[1][1]=1;

    B1.mat[0][1]=B1.mat[1][0]=0;

    B2.mat[0][0]=0,B2.mat[0][1]=2;

    B2.mat[1][0]=1,B2.mat[1][1]=-1;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%I64d%I64d",&n,&m);

        Mat ans;

        if(n%2==0) ans=((A^n)-B1)^(m-1);

        else ans=((A^n)-B2)^(m-1);

        printf("%I64d\n",(ans.mat[1][0]+ans.mat[1][1])%Mod);

    }

    return 0;

}