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.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class D {

    static int[][][] dp;
    static int[][] s;
    static int[] f;

    static int N;
    static int K;
    static int MOD = 1000000007;

    public static int f(int flag, int k, int n) {
        if (n < 0)
            return 0;
        if (k == 0)
            return n == 0 ? 1 : 0;
        if (dp[flag][k][n] != -1)
            return dp[flag][k][n];
        return dp[flag][k][n] = (flag * f(0, k - 1, n) + f(1, k, n - k)) % MOD;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        dp = new int[2][1000 + 5][1000 + 5];
        for (int[][] a : dp)
            for (int[] b : a)
                Arrays.fill(b, -1);

        s = new int[1000 + 5][1000 + 5];
        f = new int[1000 + 5];
        f[0] = 1;
        for (int i = 1; i < f.length; i++)
            f[i] = (int) ((1L * i * f[i - 1]) % MOD);
        s[0][0] = 1;
        for (int i = 1; i < s.length; i++) {
            s[i][0] = 1;
            for (int j = 1; j < s[i].length; j++)
                s[i][j] = (s[i - 1][j] + s[i][j - 1]) % MOD;
        }
        int tc = Integer.parseInt(in.readLine());
        while (tc-- > 0) {
            StringTokenizer strtok = new StringTokenizer(in.readLine());;
            N = Integer.parseInt(strtok.nextToken());
            K = Integer.parseInt(strtok.nextToken());
            int result = 0;
            for (int i = K - 1; i <= N; i++) {
                int A = f(1, K, N - 1 - i);
                int B = s[K + 1][i - (K - 1)];
                int C = f[K];
                int mul = (int) ((1L * A * B % MOD * C) % MOD);
                result = (result + mul) % MOD;
            }
            out.append(result + "\n");
        }
        System.out.print(out);
    }
}
