#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cassert>

using namespace std;

#define MEM(a,b) memset(a,(b),sizeof(a))
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))

#define MP make_pair
#define pb push_back

#define M    1000000007
#define maxn 1000000000
#define maxm 30
#define maxt 10


typedef long long  LL;

LL maxp = 1;
int m;

struct matrix
{
    int m[60][60];
};

void multiply(matrix &A,matrix &B,matrix &C)
{
	int i,j,k;


	for(i=0;i<2*m;i++)
		for(j=0;j<2*m;j++)
        {
            LL v=0;
       
            for(k=0;k<2*m;k++)
            {
                v += (LL)A.m[i][k]*B.m[k][j] ;
                if(v>=maxp) v%=M;
            }
            C.m[i][j]=v%M;

        }
}

matrix base,now,tmp;

int main()
{
   int i,j,k,n,T;

    for(i=0;i<17;i++) maxp*=10;


   scanf("%d",&T);
   assert(T>=1 && T<=maxt);

  while(T--)
  {
      scanf("%d%d",&n,&m);
      assert(n>=1 && n<=maxn && m>=1 && m<=maxm);

      MEM(base.m,0);

	 // entry x corresponds to staying at column x of an odd row if x<m
	 // entry x corresponds to staying at column x-m of even odd row if x>=m
      for(i=0;i<m;i++)
      {
	      // ways to go from the current odd row to the next even row
          if(i-1>=0) base.m[i][i-1+m]=1; 
          if(i+1<m)  base.m[i][i+1+m]=1;
		 // ways to go from the current even row the next odd row
          if(i-1>=0) base.m[i+m][i-1]=1;
          base.m[i+m][i]=1;
          if(i+1<m)  base.m[i+m][i+1]=1;
      }

      int ans=0,msb=0;

      --n;

      for(i=30;i>=0;i--)
      {
          if(n&(1<<i))
          {
              if(msb==0)
                  now=base;
              else
              {
                  multiply(now,now,tmp);now=tmp;
                  multiply(now,base,tmp);now=tmp;
              }
              msb=1;
          }
          else
          {
              if(msb==0) continue;
              multiply(now,now,tmp);now=tmp;
          }
      }

      for(i=0;i<m;i++)
         for(j=0;j<2*m;j++)
         {
             ans=(ans+now.m[i][j])%M;
         }
    if(n==0) ans=m;
    printf("%d\n",ans);

  }


	return 0;
}