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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Solver {

	public static void main(String[] Args) throws NumberFormatException,
			IOException {
		new Solver().Run();
	}

	PrintWriter pw;
	StringTokenizer Stok;
	BufferedReader br;

	public String nextToken() throws IOException {
		while (Stok == null || !Stok.hasMoreTokens()) {
			Stok = new StringTokenizer(br.readLine());
		}
		return Stok.nextToken();
	}

	public int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(nextToken());
	}

	public double nextDouble() throws NumberFormatException, IOException {
		return Double.parseDouble(nextToken());
	}

	public long nextLong() throws NumberFormatException, IOException {
		return Long.parseLong(nextToken());
	}

	final long del=(long)1e9+7;
	final long maxN=1000;
	final long maxPair=50;
	int kolQuery;
	long[] fact;
	long[][] mnozh, resMnozh;
	long[][] C;
	
	public void Run() throws NumberFormatException, IOException {
		//br = new BufferedReader(new FileReader("input.txt")); pw = new PrintWriter("output.txt");
		br=new BufferedReader(new InputStreamReader(System.in));  pw=new PrintWriter(new OutputStreamWriter(System.out));
		
		kolQuery=nextInt();
		fact=new long[(int) (maxN+1)];
		fact[1]=1;
		for (int i=2; i<=maxN; i++){
			fact[i]=(fact[i-1]*i)%del;
		}
		
		mnozh=new long[(int) (maxPair+1)][(int) (maxN+1)];
		for (int i=0; i<=maxN; i++){
			mnozh[1][i]=1;
		}
		for (int i=2; i<=maxPair; i++){
			for (int j=0; j<=maxN; j++){
				int curBuf=j;
				while (curBuf>=0){
					mnozh[i][j]+=mnozh[i-1][curBuf];
					curBuf-=i;
				}
				mnozh[i][j]%=del;
			}
		}
		
		C=new long[(int) (maxN+maxPair+1)][(int) (maxN+maxPair+1)];
		for (int i=0; i<maxN+maxPair+1; i++){
			C[i][0]=1;
			C[0][i]=1;
		}
		for (int i=1; i<=maxN+maxPair; i++){
			for (int j=1; j<=maxN+maxPair; j++){
				C[i][j]=(C[i-1][j]+C[i][j-1])%del;
			}
		}
		
		resMnozh=new long[(int) (maxPair+1)][(int) (maxN+1)];
		for (int i=1; i<=maxPair; i++){
			for (int j=0; j<=maxN; j++){
				for (int z=0; z<=j; z++){
					resMnozh[i][j]+=(mnozh[i][z]*C[j-z][i])%del;
				}
				resMnozh[i][j]%=del;
			}
		}
		for (int i=0; i<kolQuery; i++){
			int num=nextInt();
			int kolPairs=nextInt();
			int bufer=num-1-(kolPairs-1)*kolPairs/2-(kolPairs-1);
			if (bufer<0)
				pw.println(0);
			else {
				long result=(resMnozh[kolPairs][bufer]*fact[kolPairs])%del;
				pw.println(result);
			}
		}
		pw.flush();
		pw.close();
	}

}
