#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long int d[50][1100], c[2000][2000], d1[50][1100];
long long int f[50];
long long int cc(int q, int w) {
  if (q < 0) return 0;
  return c[q][w];
}
void solve(int n) {
  int b, p, i, a[30], j, q, w;
  long long int ans, s;
  for (i = 0; i < 50; i++)
    for (j = 0; j < 1100; j++) {
      d[i][j] = 0;
    }
  d[0][0] = 1;
  for (i = 0; i < 1100; i++) {
    for (p = 0; p < 50; p++)
      for (j = 0; j < 1100; j++) {
        d1[p][j] = 0;
      }
    for (p = 1; p < 50; p++)
      for (j = 0; j < 1100; j++)
        if (i + j < 1100) d1[p][j + i] = (d1[p][j + i] + d[p - 1][j]) % mod;
    for (p = 0; p < 50; p++)
      for (j = 0; j < 1100; j++) {
        d[p][j] = (d[p][j] + d1[p][j]) % mod;
      }
  }
  for (i = 0; i < 2000; i++) {
    c[i][0] = 1;
    c[0][i] = 1;
  }
  for (i = 1; i < 2000; i++)
    for (j = 1; j < 2000; j++) c[i][j] = (c[i - 1][j] + c[i][j - 1]) % mod;
  f[0] = 1;
  for (i = 1; i < 50; i++) f[i] = (f[i - 1] * i) % mod;
  for (i = 0; i < n; i++) {
    scanf("%d%d", &q, &w);
    q -= w;
    ans = 0;
    if (w > 49) {
      printf("0\n");
    } else {
      for (j = 0; j <= q; j++) {
        s = (d[w][j] * f[w]) % mod;
        s = (s * cc(q - j, w)) % mod;
        ans = (ans + s) % mod;
      }
      printf("%I64d\n", ans);
    }
  }
}
int main() {
  int n, m, x, y, i, j, q = 0;
  while (scanf("%d", &n) != EOF) {
    solve(n);
    printf("\n");
  }
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long int d[50][1100], c[2000][2000], d1[50][1100];
long long int f[50];
long long int cc(int q, int w) {
  if (q < 0) return 0;
  return c[q][w];
}
void solve(int n) {
  int b, p, i, a[30], j, q, w;
  long long int ans, s;
  for (i = 0; i < 50; i++)
    for (j = 0; j < 1100; j++) {
      d[i][j] = 0;
    }
  d[0][0] = 1;
  for (i = 0; i < 1100; i++) {
    for (p = 0; p < 50; p++)
      for (j = 0; j < 1100; j++) {
        d1[p][j] = 0;
      }
    for (p = 1; p < 50; p++)
      for (j = 0; j < 1100; j++)
        if (i + j < 1100) d1[p][j + i] = (d1[p][j + i] + d[p - 1][j]) % mod;
    for (p = 0; p < 50; p++)
      for (j = 0; j < 1100; j++) {
        d[p][j] = (d[p][j] + d1[p][j]) % mod;
      }
  }
  for (i = 0; i < 2000; i++) {
    c[i][0] = 1;
    c[0][i] = 1;
  }
  for (i = 1; i < 2000; i++)
    for (j = 1; j < 2000; j++) c[i][j] = (c[i - 1][j] + c[i][j - 1]) % mod;
  f[0] = 1;
  for (i = 1; i < 50; i++) f[i] = (f[i - 1] * i) % mod;
  for (i = 0; i < n; i++) {
    scanf("%d%d", &q, &w);
    q -= w;
    ans = 0;
    if (w > 49) {
      printf("0\n");
    } else {
      for (j = 0; j <= q; j++) {
        s = (d[w][j] * f[w]) % mod;
        s = (s * cc(q - j, w)) % mod;
        ans = (ans + s) % mod;
      }
      printf("%I64d\n", ans);
    }
  }
}
int main() {
  int n, m, x, y, i, j, q = 0;
  while (scanf("%d", &n) != EOF) {
    solve(n);
    printf("\n");
  }
  return 0;
}

```