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.*;
import java.text.DecimalFormat;
import java.util.*;

public class Main {
	static int mod = (int)1e9+7;
	static int inf = (int)(2e9+1e8);
	static double eps = 1e-15;
	static int N = 2005;
	long[][] dp = new long[N][N], C = new long[N][N];
	long[] fac = new long[N];
	void pre() {
		fac[0] = 1;
		for(int i = 1; i < N; i ++) {
			fac[i] = fac[i-1]*i%mod;
		}
		for(int i = 0; i < N; i ++) {
			C[i][0] = C[i][i] = 1;
			for(int j = 1; j < i; j ++) {
				C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
			}
		}
		dp[0][0] = 1;
		for(int i = 1; i < N; i ++) {
			dp[i][0] = 0;
			for(int j = 1; j <= i; j ++) {
				dp[i][j] = (dp[i-j][j] + dp[i-j][j-1]) % mod;
			}
		}
	}
    void work() throws Exception {
    	pre();
    	int T = nextInt();
    	while(T-- > 0) {
    		int n = nextInt();
    		int k = nextInt();
    		long ans = 0;
    		for(int i = k*(k+1)/2; i <= n; i ++) {
    			ans = (ans + dp[i][k]*C[n-i+k][k]) % mod;
    		}
    		ans = ans * fac[k] % mod;
    		out.println(ans);
    	}
    	
    	
    }  
    static PrintWriter out = new PrintWriter(System.out);
  //  Scanner cin = new Scanner(System.in);
  
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));;
    StringTokenizer str = null;
    private String next() throws Exception{
    	while (str == null || !str.hasMoreElements())
    	    str = new StringTokenizer(in.readLine());
    	return str.nextToken();
    } 
    private int nextInt() throws Exception{
    	return Integer.parseInt(next());
    }
    private long nextLong() throws Exception{
    	return Long.parseLong(next());
    }
    static int dx[] = {0,1,0,-1};
    static int dy[] = {1,0,-1,0};
    class pair implements Comparable<pair>{
    	int first, second;
    	pair(int x, int y) {
    		first = x;
    		second = y;
    	}
		public int compareTo(pair o) {
			// TODO auto-generated method stub
			if(first != o.first) return ((Integer)first).compareTo(o.first);
			else return ((Integer)second).compareTo(o.second); 
		}
    }
    int upper_bound(int[] A, int l, int r, int val) {// upper_bound(A+l,A+r,val)-A;
    	int pos = r;
    	r--;
    	while (l <= r) {
	    	int mid = (l + r) >> 1;
	    	if (A[mid] <= val) {
	    		l = mid + 1;
	    	} else {
	    		pos = mid;
	    		r = mid - 1;
	    	}
    	}
    	return pos;
    }
    int lower_bound(int[] A, int l, int r, int val) {// upper_bound(A+l,A+r,val)-A;
		int pos = r;
		r--;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (A[mid] < val) {
				l = mid + 1;
			} else {
				pos = mid;
				r = mid - 1;
			}
		}
		return pos;
	}
    
    DecimalFormat df=new DecimalFormat("0.0000000000");
    public static void main(String[] args) throws Exception{
        Main wo = new Main();
        wo.work();
        out.close();
    }
}