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

public class D {
  static long M = 1000000007L;
  static long M(long x, long y) { return (x*y)%M; }
  static long A(long x, long y) { return (x+y)%M; }

  public static void main(String[] args) throws Exception {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(in.readLine());
    StringBuilder out = new StringBuilder();

    CAS: for(int cas=0; cas<T; cas++) {
      String[] arr = in.readLine().split(" ");
      int n = Integer.parseInt(arr[0]);
      int k = Integer.parseInt(arr[1]);

      int new_n = n;
      new_n -= k-1; //gap between pairs
      new_n--; //sequences start at 1
      long ans = M(factorial(k), f(k, new_n, true));
      /*
      if(ans != slow(n, k)) {
        System.out.println(n+" "+k+" "+ans+" "+slow(n, k));
        throw new RuntimeException();
      }*/
      out.append(ans);
      out.append("\n");
    }
    System.out.print(out);
  }

  static Long[] FACT = new Long[1001];
  static long factorial(int n) {
    if(FACT[n]!=null) return FACT[n];

    long ans = 1;
    for(long i=1; i<=n; i++)
      ans = M(ans, i);
    return FACT[n]=ans;
  }

  static Long[][][] F = new Long[50][1001][2];
  static long f(int k, int n, boolean first) {
    int min_space = 0;
    for(int i=0; i<k; i++)
      min_space += i;
    if(min_space > n) return 0;

    if(k==0) return 1;

    if(F[k][n][first?1:0]!=null) return F[k][n][first?1:0];
    long ans = 0;

    for(int gap=0; gap<=n; gap++) {
      int nk = gap/k;
      if(nk==0 && !first) continue;
      ans = A(ans, (first?nk+1:nk)*f(k-1, n-gap, false));
    }

    /*
    for(int gap=(first?0:1); gap*k <= n; gap++) {
      for(int extra_gap=0; extra_gap + gap*k<=n; extra_gap++)
        ans = A(ans, f(k-1, n-gap*k-extra_gap, false));
    }
    */
    return F[k][n][first?1:0] = ans;
  }

  static long slow(int n, int k) {
    return slow_rec(n, k, 0, 1, new HashSet<Integer>(), new ArrayList<Integer>());
  }
  static long slow_rec(int n, int k, int i, int a_lo, Set<Integer> D, List<Integer> S) {
    if(i==k) {
      return 1;
    }

    long ans = 0;
    for(int ai=a_lo; ai<=n; ai++) {
      for(int bi=ai; bi<=n; bi++) {
        int d = bi-ai;
        if(D.contains(d)) continue;
        Set<Integer> D2 = new HashSet<Integer>(D);
        D2.add(d);
        List<Integer> S2 = new ArrayList<Integer>(S);
        S2.add(ai);
        S2.add(bi);
        ans += slow_rec(n, k, i+1, bi+1, D2, S2);
      }
    }
    return ans;
  }
}
