The sequence of integer pairs (a1, b1), (a2, b2), ..., (ak, bk) is beautiful, if the following statements are fulfilled: 

  * 1 ≤ a1 ≤ b1 < a2 ≤ b2 < ... < ak ≤ bk ≤ n, where n is a given positive integer; 
  * all numbers b1 - a1, b2 - a2, ..., bk - ak are distinct. 



For the given number n find the number of beautiful sequences of length k. As the answer can be rather large, print the remainder after dividing it by 1000000007 (109 + 7).

Input

The first line contains integer t (1 ≤ t ≤ 2·105) — the number of the test data.

Each of the next t lines contains two integers n and k (1 ≤ k ≤ n ≤ 1000).

Output

For each test from the input print the answer to the problem modulo 1000000007 (109 + 7). Print the answers to the tests in the order in which the tests are given in the input.

Examples

Input

6
1 1
2 1
2 2
3 1
3 2
3 3


Output

1
3
0
6
2
0

Note

In the first test sample there is exactly one beautiful sequence: (1, 1).

In the second test sample, the following sequences are beautiful: 

  * (1, 1); 
  * (1, 2); 
  * (2, 2). 



In the fourth test sample, the following sequences are beautiful: 

  * (1, 1); 
  * (1, 2); 
  * (1, 3); 
  * (2, 2); 
  * (2, 3); 
  * (3, 3). 



In the fifth test sample, the following sequences are beautiful: 

  * (1, 1), (2, 3); 
  * (1, 2), (3, 3). 



In the third and sixth samples, there are no beautiful sequences.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;

public class D {
    static int maxn=1000, maxk=50;
    static long mod=1000000007;
    
    static long[][] unique_compositions() {
        long[][] 
                cu=new long[maxn+1][maxn+1],
                ne=new long[maxn+1][maxn+1],
                kn=new long[maxk+1][maxn+1];

        for (int i=0; i<=maxn; i++) {
            cu[i][i]=1;
            kn[1][i]=1;
        }
        
        for (int k=2; k<=maxk; k++) {
            ne[0][0]=0;
            for (int m=1; m<=maxn; m++) {
                for (int n=m; n<=maxn; n++) {
                    
                    ne[m][n]=ne[m-1][n-1]+cu[m-1][n-m];
                    if (ne[m][n]>=mod) {
                        ne[m][n]-=mod;
                    }
                    
                    kn[k][n]+=ne[m][n];
                    if (kn[k][n]>=mod) {
                        kn[k][n]-=mod;
                    }
                }
            }
            
            long[][] tmp=cu; cu=ne; ne=tmp;
        }
        
        return kn;
    }
    
    static long[][] compositions() {
        long[][] kn=new long[maxk+1][maxn+1];
        Arrays.fill(kn[1],1,kn[1].length,1);
        for (int k=2; k<=maxk; k++) {
            for (int n=k; n<=maxn; n++) {
                
                kn[k][n]=kn[k][n-1]+kn[k-1][n-1];
                if (kn[k][n]>=mod) {
                    kn[k][n]-=mod;
                }
            }
        }
        
        return kn;
    }
    
    static long[] factorials() {
        long[] fact=new long[maxk+1]; fact[0]=1;
        for (int i=1; i<=maxk; i++) {
            fact[i]=fact[i-1]*i;
            if (fact[i]>=mod) {
                fact[i]=fact[i]%mod;
            }
        }
        return fact;
    }
    
    static long product(long...l) {
        long ret=1;
        for (int i=0; i<l.length; i++) {
            ret*=l[i];
            if(ret>=mod) {
                ret=ret%mod;
            }
        }
        return ret;
    }
    
    static void solve(int[] qn, int[] qk) {
        long[][] comp=compositions();
        long[][] ucomp=unique_compositions();
        long[] fact=factorials();
        
        long[][] f=new long[maxk+1][maxn+1];
        for (int k=1; k<=maxk; k++) {
            for (int n=k; n<=maxn; n++) {
                for (int i=0; i<=n; i++) {
                    f[k][n]+=product(fact[k],ucomp[k][i],comp[k][n-i]);//last b==n
                    if (f[k][n]>=mod) {
                        f[k][n]-=mod;
                    }
                    
                    if(k<maxk) {
                        f[k][n]+=product(fact[k],ucomp[k][i],comp[k+1][n-i]);//last b<n
                        if (f[k][n]>=mod) {
                            f[k][n]-=mod;
                        }
                    }
                }
            }
        }
        
        
        sb.setLength(0);
        
        int t=qn.length;
        for (int i=0; i<t; i++) {
            if(qk[i]<=maxk) {
                sb.append(f[qk[i]][qn[i]]+"\n");
            } else {
                sb.append("0\n");
            }
        }
        
        System.out.println(sb.toString());
    }

    
    
    
    
    static StringBuilder sb=new StringBuilder();
    static void parse(String l, int[] here) {
        sb.setLength(0);
        int len=l.length(), j=0;
        for (int i=0; i<len; i++) {
            char c=l.charAt(i);
            if(c==' ') {
                here[j++]=Integer.parseInt(sb.toString());
                sb.setLength(0);
            } else {
                sb.append(c);
            }
        }
        if(sb.length()>0) {
            here[j++]=Integer.parseInt(sb.toString());
        }
    }
    
    static void run_stream(InputStream ins) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int t=Integer.parseInt(br.readLine());
        int[] qn=new int[t], qk=new int[t];
        for (int i=0; i<t; i++) {
            String s=br.readLine();
            int space=s.indexOf(' ');
            qn[i]=Integer.parseInt(s.substring(0, space));
            qk[i]=Integer.parseInt(s.substring(space+1));
        }
        
        long t0=System.currentTimeMillis();
        solve(qn,qk);
        //System.out.println(System.currentTimeMillis()-t0);
    }

    public static void main(String[] args) throws IOException {
        run_stream(System.in);
    }

    
    
    
    
    
    
    
    static void solve_bak(int[] qn, int[] qk) {
        long[][] 
                cab=new long[maxn+1][maxn+1],
                nab=new long[maxn+1][maxn+1],
                to =new long[maxn+1][maxn+1],
                kn =new long[maxn+1][maxn+1];
        
        for (int c=1; c<=maxn; c++) {
            for (int r=c; r>0; r--) {
                cab[r][c]=1;
                to[r][c]=cab[r][c]+r<maxn? to[r+1][c]: 0;
            }
            kn[1][c]=to[1][c];
        }
        
        long fac=1;
        for (int k=2; k<=maxn; k++) {
            fac*=k;
            if(fac>=mod) {
                fac-=mod;
            }
            
            for (int r=1; r<=maxn; r++) {
                for (int c=r; c<=maxn; c++) {
                    nab[r][c]=cab[r-1][c-1]+(r-(c-r)>0? to[r-(c-r)][r-1]: 0);
                    if(nab[r][c]>=mod) {
                        nab[r][c]-=mod;
                    }
                }
            }
            
            for (int n=1; n<=maxn; n++) {
                for (int a=1; a<=n; a++) {
                    kn[k][n]+=nab[a][n];
                    if(kn[k][n]>=mod) {
                        kn[k][n]-=mod;
                    }
                }
                kn[k][n]*=fac;
                if(kn[k][n]>=mod) {
                    kn[k][n]-=mod;
                }
            }
            
            long[][] tmp=cab; cab=nab; nab=tmp;
            for (int c=1; c<=maxn; c++) {
                for (int r=c; r>0; r--) {
                    to[r][c]=cab[r][c]+r<maxn? to[r+1][c]: 0;
                }
            }
        }
        
        
        
        
        sb.setLength(0);
        
        int t=qn.length;
        for (int i=0; i<t; i++) {
            sb.append(kn[qk[i]][qn[i]]+"\n");
        }
        
        System.out.println(sb.toString());
    }

}
