#include <bits/stdc++.h>
#pragma comment(linker, "/stack:32000000")
using namespace std;
const int INF = 2147483647;
const long long LLINF = 9223372036854775807LL;
const int maxn = 1010;
const int maxk = 50;
const int mod = 1000000007;
struct num {
  int x;
  num() : x(0) {}
  num(int x) : x(x) {}
  num operator+(const num &o) const {
    num res(x + o.x);
    if (res.x >= mod) res.x -= mod;
    return res;
  }
  num operator-(const num &o) const {
    num res(x - o.x);
    if (res.x < 0) res.x += mod;
    return res;
  }
  num operator*(const num &o) const {
    num res(x * (long long)o.x % mod);
    return res;
  }
};
num comb[maxn * 2][maxn * 2];
num dp1[2][maxn][maxn];
num dp2[maxk][maxn];
num fact[maxn];
int main() {
  fact[0] = num(1);
  for (int i = 1; i < maxn; ++i) fact[i] = fact[i - 1] * num(i);
  for (int i = 0; i < maxn * 2; ++i) comb[i][0] = num(1);
  for (int i = 1; i < maxn * 2; ++i)
    for (int j = 1; j < maxn * 2; ++j)
      comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
  int cr = 0;
  int nx = 1;
  for (int i = 0; i < maxn; ++i) dp1[cr][0][i] = num(1);
  for (int k = 1; k < maxk; ++k) {
    for (int i = 0; i < maxn; ++i)
      for (int j = 0; j < maxn; ++j) {
        if (!j) {
          dp1[nx][i][j] = num(0);
          continue;
        }
        dp1[nx][i][j] = dp1[nx][i][j - 1];
        int toi = i - j;
        if (toi >= 0) dp1[nx][i][j] = dp1[nx][i][j] + dp1[cr][toi][j - 1];
      }
    swap(cr, nx);
    for (int i = 1; i < maxn; ++i)
      for (int j = 1; j < maxn; ++j) {
        int rem = i - j;
        if (rem < 0) continue;
        if (rem + k >= maxn) continue;
        dp2[k][i] =
            dp2[k][i] + dp1[cr][j][maxn - 1] * comb[rem + k][rem] * fact[k];
      }
  }
  int t;
  scanf("%d", &t);
  while (t--) {
    int curn, curk;
    scanf("%d%d", &curn, &curk);
    printf("%d\n", dp2[curk][curn]);
  }
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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>
#pragma comment(linker, "/stack:32000000")
using namespace std;
const int INF = 2147483647;
const long long LLINF = 9223372036854775807LL;
const int maxn = 1010;
const int maxk = 50;
const int mod = 1000000007;
struct num {
  int x;
  num() : x(0) {}
  num(int x) : x(x) {}
  num operator+(const num &o) const {
    num res(x + o.x);
    if (res.x >= mod) res.x -= mod;
    return res;
  }
  num operator-(const num &o) const {
    num res(x - o.x);
    if (res.x < 0) res.x += mod;
    return res;
  }
  num operator*(const num &o) const {
    num res(x * (long long)o.x % mod);
    return res;
  }
};
num comb[maxn * 2][maxn * 2];
num dp1[2][maxn][maxn];
num dp2[maxk][maxn];
num fact[maxn];
int main() {
  fact[0] = num(1);
  for (int i = 1; i < maxn; ++i) fact[i] = fact[i - 1] * num(i);
  for (int i = 0; i < maxn * 2; ++i) comb[i][0] = num(1);
  for (int i = 1; i < maxn * 2; ++i)
    for (int j = 1; j < maxn * 2; ++j)
      comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
  int cr = 0;
  int nx = 1;
  for (int i = 0; i < maxn; ++i) dp1[cr][0][i] = num(1);
  for (int k = 1; k < maxk; ++k) {
    for (int i = 0; i < maxn; ++i)
      for (int j = 0; j < maxn; ++j) {
        if (!j) {
          dp1[nx][i][j] = num(0);
          continue;
        }
        dp1[nx][i][j] = dp1[nx][i][j - 1];
        int toi = i - j;
        if (toi >= 0) dp1[nx][i][j] = dp1[nx][i][j] + dp1[cr][toi][j - 1];
      }
    swap(cr, nx);
    for (int i = 1; i < maxn; ++i)
      for (int j = 1; j < maxn; ++j) {
        int rem = i - j;
        if (rem < 0) continue;
        if (rem + k >= maxn) continue;
        dp2[k][i] =
            dp2[k][i] + dp1[cr][j][maxn - 1] * comb[rem + k][rem] * fact[k];
      }
  }
  int t;
  scanf("%d", &t);
  while (t--) {
    int curn, curk;
    scanf("%d%d", &curn, &curk);
    printf("%d\n", dp2[curk][curn]);
  }
  return 0;
}

```