#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
const int MN = 2000;
const int Mo = 1000000007;
set<int> bad;
int n, m;
long long f[MN][MN];
long long g[MN][MN];
long long a[MN][MN];
long long frac[MN];
long long qm(long long s, long long t) {
  if (t == 0) return 1;
  if (t == 1) return s;
  long long res = qm(s, t / 2);
  res = (res * res) % Mo;
  if (t & 1) res = (res * s) % Mo;
  return res;
}
long long A(long long n, long long m) {
  return frac[n] * qm(frac[n - m], Mo - 2) % Mo;
}
int main() {
  int i, j, k, w, u, t;
  for (i = 0; i <= 1000; i++) f[1][i] = i + 1;
  w = 0;
  for (i = 2; i <= 1000; i++) {
    w += i - 1;
    for (j = w; j <= 1000; j++)
      for (k = 0; k <= 1000; k++) {
        u = j - k - (k + 1) * (i - 1);
        if (u < 0) break;
        f[i][j] = (f[i][j] + f[i - 1][u]) % Mo;
      }
  }
  for (i = 1; i <= 1000; i++) {
    g[i][0] = f[i][0];
    for (j = 1; j <= 1000; j++) g[i][j] = (f[i][j] - f[i][j - 1] + Mo) % Mo;
  }
  frac[0] = 1;
  for (i = 1; i <= 1000; i++) frac[i] = (frac[i - 1] * i) % Mo;
  for (i = 1; i <= 1000; i++)
    for (j = 1; j <= i; j++) a[i][j] = A(i, j);
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &m);
    long long res = 0;
    for (i = 0; i <= n; i++)
      if (g[m][i] > 0 && n - i >= m) res = (res + g[m][i] * a[n - i][m]) % Mo;
    printf("%d\n", (int)res);
  }
  return 0;
}

### Prompt

Generate 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 INF = 1e8;
const int MN = 2000;
const int Mo = 1000000007;
set<int> bad;
int n, m;
long long f[MN][MN];
long long g[MN][MN];
long long a[MN][MN];
long long frac[MN];
long long qm(long long s, long long t) {
  if (t == 0) return 1;
  if (t == 1) return s;
  long long res = qm(s, t / 2);
  res = (res * res) % Mo;
  if (t & 1) res = (res * s) % Mo;
  return res;
}
long long A(long long n, long long m) {
  return frac[n] * qm(frac[n - m], Mo - 2) % Mo;
}
int main() {
  int i, j, k, w, u, t;
  for (i = 0; i <= 1000; i++) f[1][i] = i + 1;
  w = 0;
  for (i = 2; i <= 1000; i++) {
    w += i - 1;
    for (j = w; j <= 1000; j++)
      for (k = 0; k <= 1000; k++) {
        u = j - k - (k + 1) * (i - 1);
        if (u < 0) break;
        f[i][j] = (f[i][j] + f[i - 1][u]) % Mo;
      }
  }
  for (i = 1; i <= 1000; i++) {
    g[i][0] = f[i][0];
    for (j = 1; j <= 1000; j++) g[i][j] = (f[i][j] - f[i][j - 1] + Mo) % Mo;
  }
  frac[0] = 1;
  for (i = 1; i <= 1000; i++) frac[i] = (frac[i - 1] * i) % Mo;
  for (i = 1; i <= 1000; i++)
    for (j = 1; j <= i; j++) a[i][j] = A(i, j);
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &m);
    long long res = 0;
    for (i = 0; i <= n; i++)
      if (g[m][i] > 0 && n - i >= m) res = (res + g[m][i] * a[n - i][m]) % Mo;
    printf("%d\n", (int)res);
  }
  return 0;
}

```