#include <bits/stdc++.h>
using namespace std;
const volatile auto INIT = [] {
  return ios::sync_with_stdio(false), cin.tie(nullptr);
}();
constexpr int MO = 1000 * 1000 * 1000 + 7;
void Ok(int& a) {
  if (a >= MO) a -= MO;
}
int Mult(int a, int b) { return 1ll * a * b % MO; }
int Power(int a, int64_t b) {
  int res = 1;
  for (; b > 0; b >>= 1, a = Mult(a, a)) {
    if (b & 1) {
      res = Mult(res, a);
    }
  }
  return res;
}
constexpr int NN = 3010;
int fact[NN], invfact[NN];
void Init() {
  fact[0] = invfact[0] = 1;
  for (int i = 1; i < NN; ++i) {
    fact[i] = Mult(fact[i - 1], i);
    invfact[i] = Power(fact[i], MO - 2);
  }
}
int Comb(int n, int k) {
  if (n < 0 || k < 0 || k > n) return 0;
  return Mult(fact[n], Mult(invfact[n - k], invfact[k]));
}
constexpr int N = 1010;
constexpr int K = 50;
int dp[K][N][N];
int main() {
  Init();
  for (int i = 0; i < N; ++i) {
    dp[1][i][i] = 1;
  }
  for (int j = 0; j < N; ++j) {
    for (int k = 1; k < N; ++k) {
      Ok(dp[1][j][k] += dp[1][j][k - 1]);
    }
  }
  for (int i = 2; i < K; ++i) {
    for (int j = 1; j < N; ++j) {
      for (int k = 1; k <= j; ++k) {
        if (j - k >= 0) {
          dp[i][j][k] = dp[i - 1][j - k][k - 1];
        }
      }
    }
    for (int j = 0; j < N; ++j) {
      for (int k = 1; k < N; ++k) {
        Ok(dp[i][j][k] += dp[i][j][k - 1]);
      }
    }
  }
  for (int i = 0; i < K; ++i) {
    for (int j = 0; j < N; ++j) {
      for (int k = 0; k < N; ++k) {
        dp[i][j][k] = Mult(dp[i][j][k], fact[i]);
      }
    }
  }
  int tc;
  cin >> tc;
  while (tc--) {
    int n, k;
    cin >> n >> k;
    if (k >= K) {
      cout << 0 << '\n';
    } else {
      int ans = 0;
      for (int i = 0; i <= n; ++i) {
        Ok(ans += Mult(dp[k][i][N - 1], Comb(n - i, k)));
      }
      cout << ans << '\n';
    }
  }
  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 volatile auto INIT = [] {
  return ios::sync_with_stdio(false), cin.tie(nullptr);
}();
constexpr int MO = 1000 * 1000 * 1000 + 7;
void Ok(int& a) {
  if (a >= MO) a -= MO;
}
int Mult(int a, int b) { return 1ll * a * b % MO; }
int Power(int a, int64_t b) {
  int res = 1;
  for (; b > 0; b >>= 1, a = Mult(a, a)) {
    if (b & 1) {
      res = Mult(res, a);
    }
  }
  return res;
}
constexpr int NN = 3010;
int fact[NN], invfact[NN];
void Init() {
  fact[0] = invfact[0] = 1;
  for (int i = 1; i < NN; ++i) {
    fact[i] = Mult(fact[i - 1], i);
    invfact[i] = Power(fact[i], MO - 2);
  }
}
int Comb(int n, int k) {
  if (n < 0 || k < 0 || k > n) return 0;
  return Mult(fact[n], Mult(invfact[n - k], invfact[k]));
}
constexpr int N = 1010;
constexpr int K = 50;
int dp[K][N][N];
int main() {
  Init();
  for (int i = 0; i < N; ++i) {
    dp[1][i][i] = 1;
  }
  for (int j = 0; j < N; ++j) {
    for (int k = 1; k < N; ++k) {
      Ok(dp[1][j][k] += dp[1][j][k - 1]);
    }
  }
  for (int i = 2; i < K; ++i) {
    for (int j = 1; j < N; ++j) {
      for (int k = 1; k <= j; ++k) {
        if (j - k >= 0) {
          dp[i][j][k] = dp[i - 1][j - k][k - 1];
        }
      }
    }
    for (int j = 0; j < N; ++j) {
      for (int k = 1; k < N; ++k) {
        Ok(dp[i][j][k] += dp[i][j][k - 1]);
      }
    }
  }
  for (int i = 0; i < K; ++i) {
    for (int j = 0; j < N; ++j) {
      for (int k = 0; k < N; ++k) {
        dp[i][j][k] = Mult(dp[i][j][k], fact[i]);
      }
    }
  }
  int tc;
  cin >> tc;
  while (tc--) {
    int n, k;
    cin >> n >> k;
    if (k >= K) {
      cout << 0 << '\n';
    } else {
      int ans = 0;
      for (int i = 0; i <= n; ++i) {
        Ok(ans += Mult(dp[k][i][N - 1], Comb(n - i, k)));
      }
      cout << ans << '\n';
    }
  }
  return 0;
}

```