#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define mod 100000007

int a[500005];
inline void ADD(int & x, int y) {
    x += y; if (x >= mod) x -= mod;
}
int S(int l, int r) {
    int answer = 0;
    for (int i = l; i <= r; i ++) {
        ADD(answer, a[i]);
    }
    return answer;
}
void calc(int n, vector<int> & coeff) {
    // lo: [1..n/2]
    // hi: [n/2+1..n]
    a[0] = 0;
    for (int i = 1; i <= n; i ++) {
        a[i] = 1;
    }
    coeff[1] = S(n/2+1, n);
    for (int le = 2; coeff[le - 1] != 0; le ++) {
        for (int i = 1; i <= n; i ++) ADD(a[i], a[i - 1]);
        for (int i = n; i >= 1; i --) {
            a[i] = a[i / 2];
        }
        coeff[le] = S(n/2+1, n);
    }
}

int v[500005];
int main() {
    int tc; cin >> tc;
    for (; tc > 0; tc --) {
        int n, m;
        cin >> n >> m;
        vector<int> coeff (22);
        calc(n, coeff);
        v[0] = 1;
        for (int i = 1; i <= m; i ++) {
            v[i] = 0;
            for (int k = 0; k <= i and k <= 20; k ++) {
                v[i] = (v[i] + (long long) v[i - k] * coeff[k]) % mod;
            }
        }
        cout << v[m] << endl;
    }
    return 0;
}

import java.awt.Point;
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import static java.lang.Math.*;

public class Solution implements Runnable {

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    public static void main(String[] args) {
        new Thread(null, new Solution(), "", 256 * (1L << 20)).start();
    }

    public void run() {
        try {
            long t1 = System.currentTimeMillis();
            out = new PrintWriter(System.out);

            in = new BufferedReader(new InputStreamReader(System.in));
            //in = new BufferedReader(new FileReader("src/input.txt"));
            //   out = new PrintWriter("output.txt");

            Locale.setDefault(Locale.US);
            solve();
            in.close();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time = " + (t2 - t1));
        } catch (Throwable t) {
            t.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    // solution
    void solve() throws IOException {
        int ct = readInt();
        while (ct-- > 0) {
            solveTestCase();
        }
    }
    static final long modulo = 100000007L;

    void solveTestCase() throws IOException {
        int n = readInt();
        int wordLength = readInt();
        int maxLength = (int) (1 + Math.ceil(Math.log(n) / Math.log(2))); //science!
        FenwickTree[] f = new FenwickTree[maxLength + 1];
        for (int i = 0; i < f.length; i++) {
            f[i] = new FenwickTree(n);
        }
        f[0].increase(0, +1);
        for (int i = 1; i <= n; i++) {
            f[1].increase(i, +1);
        }
        for (int curSymbol = 1; curSymbol <= n; curSymbol++) {
            for (int curLength = 2; curLength <= maxLength; curLength++) {
                long value = f[curLength - 1].find(curSymbol / 2);
                f[curLength].increase(curSymbol, +value);
            }
        }
        long[] wordsWithLength = new long[maxLength + 1];
        for (int lastSymbol = 0; lastSymbol <= n; lastSymbol++) {
            if (lastSymbol * 2 > n) {
                for (int length = 1; length <= maxLength; length++) {
                    wordsWithLength[length] = (wordsWithLength[length] + f[length].find(lastSymbol) - f[length].find(lastSymbol - 1)) % modulo;
                }
            }
        }
       // System.out.println(Arrays.toString(wordsWithLength) + " wwl");
        long[] result = new long[wordLength + 1];
        result[0] = 1;
        for (int i = 0; i < result.length; i++) {
            for (int nextWordLength = 1; nextWordLength <= maxLength; nextWordLength++) {
                if (i + nextWordLength < result.length) {
                    result[i + nextWordLength] = (result[i + nextWordLength] + result[i] * wordsWithLength[nextWordLength]) % modulo;
                }
            }
        }
        out.println(result[wordLength]);
    }

    class FenwickTree {

        private long[] sum;

        FenwickTree(int size) {
            sum = new long[size + 2];
        }

        private int prev(int x) {
            return x & (x - 1);
        }

        private int next(int x) {
            return 2 * x - prev(x);
        }

        void increase(int id, long value) {
            id++;
            while (id < sum.length) {
                sum[id] = (sum[id] + value) % modulo;
                id = next(id);
            }
        }

        long find(int id) {
            id++;
            long res = 0;
            if (id == 0) {
                return 0;
            }
            while (id > 0) {
                res += sum[id];
                id = prev(id);
            }
            return res % modulo;
        }
    }
}

//ABC
 

# Enter your code here. Read input from STDIN. Print output to STDOUT
mod = 10**8 + 7

for cas in range(int(input())):
    n, m = map(int, input().strip().split())
    v = [2*i > n for i in range(n+1)]
    for i in range(n-1,-1,-1):
        v[i] += v[i + 1]
    c = []
    while v[1]:
        c.append(v[1])
        for i in range(1,n//2+1):
            v[i] = v[2*i]
        for i in range(n//2+1,n+1):
            v[i] = 0
        for i in range(n-1,-1,-1):
            v[i] = (v[i] + v[i + 1]) % mod

    f = [1] + [0]*(len(c)-1)
    for k in range(1,m+1):
        f = [sum(F * C for F, C in zip(f, c)) % mod] + f[:-1]

    print(f[0])

from numpy import matrix
def monoidpow(op,e,a,k):
    sq = a
    c = e
    while k>0:
        if k&1: c = op(c,sq)
        sq = op(sq,sq)
        k>>=1
    return c
for _ in xrange(input()):
    N,M = map(int,raw_input().split())
    F = [[0]*20 for _ in xrange(N+1)]
    for i in xrange(N,N/2,-1): F[i][0] = 1
    F[N/2][1] = 1+N%2
    for i in xrange(N/2-1,0,-1):
        for k in xrange(1,20):
            F[i][k]+=(F[2*i][k-1] + F[2*i+1][k-1] + F[i+1][k])%100000007
    S = [0]*20
    for j in xrange(1,N+1):
        for k in xrange(20):
            S[k] =(S[k]+F[j][k])%100000007
    A = matrix([S]+[[i==j for i in xrange(20)] for j in xrange(19)],dtype='longlong')
    A = monoidpow(lambda a,b: a*b%100000007,1,A,M)
    
    print (A*matrix([[1]]+[[0]]*19))[0,0]

#include <stdio.h>
#include <stdlib.h> 
#include <math.h> 

int main() {

    int tpm, nbtest,nb,profondeur,i,j,tot,deb,*facteur,*list,*previous,*next,*tmp,mod=100000007,flnb_2,flnb_2p1,out;
    scanf("%d", &nbtest);
    
    while(nbtest>0){
        nbtest--;
        scanf("%d %d", &nb,&profondeur);
        
        facteur=(int*) calloc(profondeur,sizeof(int));
        list=(int*) calloc(profondeur,sizeof(int));
        previous=(int*) calloc(nb+1,sizeof(int));
        next=(int*) calloc(nb+1,sizeof(int));

        flnb_2=floor(nb/2);
        flnb_2p1=flnb_2+1;
        out=0;
        for(i=1;i<=nb;i++){
            previous[i]=1;  
        }
        tot=nb-flnb_2;
        
        for(j=1;j<profondeur;j++){
            
            list[j]=tot;
            next[1]=tot;

            //printf("\n");
            //printf("\n");
            
            for(i=1;i<=j-1;i++){
                //printf("tot => %d - %d x %d ",tot ,facteur[i],list[j-i]);
            tot-=((long long)facteur[i]*(long long)list[j-i])%mod;
                if(tot<0){
                tot+=mod;
                }
                //printf(" => %d",tot);
            }
            
            //printf("\n");
            //printf("\n");
            if(tot>0){
            facteur[j]=tot;
            } else {
                out=1;
               /* 
                printf("\n"); printf("\n");
                for(i=1;i<j;i++){
                    printf("%d ",facteur[i]);
                }
                printf("\n");
                for(i=1;i<j;i++){
                   printf("%d ",list[i]);
                }
                printf("out");*/
                break;
            }
            tot=0;
            
            
            
            for(i=2;i<flnb_2p1;i=i+2){
                next[i]=(next[i-1]+previous[i>>1])%mod;
                next[i+1]=next[i];
            }
            
            if(flnb_2p1&1){
                deb=1;
                tot=(tot+next[flnb_2p1])%mod;
            } else {
                deb=0;
            }
            
            for(i=flnb_2p1+deb;i<=nb;i=i+2){
                next[i]=(next[i-1]+previous[i>>1])%mod;
   
                if(i+1<=nb){
                    next[i+1]=next[i]%mod;
                    tot=(tot+2*next[i])%mod;
                } else {
                    tot=(tot+next[i])%mod;
                }
            }
            //for(i=1;i<=nb;i=i+1){printf("%d\t",next[i]);}
            //printf("\n\n");
            tmp=previous;
            previous=next;
            next=tmp;
        }
        if(out&1){
            for(i=j+1;i<=profondeur;i++){
                list[i]=0;
                for(int k=1;k<=j;k++){
                    
                    tot=((long long)facteur[k]*(long long)list[i-k])%mod;
                    //printf("Tot: %d %d => %d + %d\n",facteur[k],list[i-k],tot,list[i]);
                list[i]=(list[i]+tot)%mod;
                
                }
            }
            tot=list[i-1];
        
        }
       
        printf("%d\n", tot);
    }   
    return 0;
}