#include <bits/stdc++.h>
using namespace std;
const int inf = 2000000000;
static inline int Rint() {
  struct X {
    int dig[256];
    X() {
      for (int i = '0'; i <= '9'; ++i) dig[i] = 1;
      dig['-'] = 1;
    }
  };
  static X fuck;
  int s = 1, v = 0, c;
  for (; !fuck.dig[c = getchar()];)
    ;
  if (c == '-')
    s = 0;
  else if (fuck.dig[c])
    v = c ^ 48;
  for (; fuck.dig[c = getchar()]; v = v * 10 + (c ^ 48))
    ;
  return s ? v : -v;
}
template <typename T>
static inline void cmax(T& a, const T& b) {
  if (b > a) a = b;
}
template <typename T>
static inline void cmin(T& a, const T& b) {
  if (b < a) a = b;
}
const int mod = 1000000007;
static inline int add(int a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
int fac[1005];
int dp[50][1005];
int comb[2005][2005];
int ans[1005][1005];
void init() {
  dp[0][0] = 1;
  for (int now = 0; now <= 1000; ++now)
    for (int k = 46; k >= 0; --k)
      for (int s = 1000 - now; s >= 0; --s)
        dp[k + 1][now + s] = add(dp[k + 1][now + s], dp[k][s]);
  fac[0] = 1;
  for (int i = 1; i <= 1000; ++i) fac[i] = (long long)fac[i - 1] * i % mod;
  for (int i = 0; i <= 2000; ++i)
    for (int j = 0; j <= i; ++j)
      if (j == 0 || j == i)
        comb[i][j] = 1;
      else
        comb[i][j] = add(comb[i - 1][j], comb[i - 1][j - 1]);
  for (int k = 1; k <= 46; ++k) {
    const long long c0 = fac[k];
    for (int s0 = 0; s0 <= 1000; ++s0)
      if (dp[k][s0] > 0) {
        const int pre = k - 1;
        const long long c1 = c0 * dp[k][s0] % mod;
        for (int n = s0 + pre; n <= 1000; ++n) {
          const int need = n - s0 - pre;
          const long long c2 = comb[k + 1 + need - 1][need];
          ans[n + 1][k] = add(ans[n + 1][k], c1 * c2 % mod);
        }
      }
  }
}
int main() {
  init();
  int cas = Rint();
  while (cas--) {
    const int n = Rint(), k = Rint();
    printf("%d\n", ans[n][k]);
  }
  return 0;
}

### Prompt

Create a solution in CPP for 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 = 2000000000;
static inline int Rint() {
  struct X {
    int dig[256];
    X() {
      for (int i = '0'; i <= '9'; ++i) dig[i] = 1;
      dig['-'] = 1;
    }
  };
  static X fuck;
  int s = 1, v = 0, c;
  for (; !fuck.dig[c = getchar()];)
    ;
  if (c == '-')
    s = 0;
  else if (fuck.dig[c])
    v = c ^ 48;
  for (; fuck.dig[c = getchar()]; v = v * 10 + (c ^ 48))
    ;
  return s ? v : -v;
}
template <typename T>
static inline void cmax(T& a, const T& b) {
  if (b > a) a = b;
}
template <typename T>
static inline void cmin(T& a, const T& b) {
  if (b < a) a = b;
}
const int mod = 1000000007;
static inline int add(int a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
int fac[1005];
int dp[50][1005];
int comb[2005][2005];
int ans[1005][1005];
void init() {
  dp[0][0] = 1;
  for (int now = 0; now <= 1000; ++now)
    for (int k = 46; k >= 0; --k)
      for (int s = 1000 - now; s >= 0; --s)
        dp[k + 1][now + s] = add(dp[k + 1][now + s], dp[k][s]);
  fac[0] = 1;
  for (int i = 1; i <= 1000; ++i) fac[i] = (long long)fac[i - 1] * i % mod;
  for (int i = 0; i <= 2000; ++i)
    for (int j = 0; j <= i; ++j)
      if (j == 0 || j == i)
        comb[i][j] = 1;
      else
        comb[i][j] = add(comb[i - 1][j], comb[i - 1][j - 1]);
  for (int k = 1; k <= 46; ++k) {
    const long long c0 = fac[k];
    for (int s0 = 0; s0 <= 1000; ++s0)
      if (dp[k][s0] > 0) {
        const int pre = k - 1;
        const long long c1 = c0 * dp[k][s0] % mod;
        for (int n = s0 + pre; n <= 1000; ++n) {
          const int need = n - s0 - pre;
          const long long c2 = comb[k + 1 + need - 1][need];
          ans[n + 1][k] = add(ans[n + 1][k], c1 * c2 % mod);
        }
      }
  }
}
int main() {
  init();
  int cas = Rint();
  while (cas--) {
    const int n = Rint(), k = Rint();
    printf("%d\n", ans[n][k]);
  }
  return 0;
}

```