#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:512000000")
using namespace std;
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline string tostr(const T& x) {
  stringstream ss;
  ss << x;
  return ss.str();
}
const long double EPS = 1e-12;
const int INF = 1000 * 1000 * 1000;
const char CINF = 102;
const long long LINF = INF * 1ll * INF;
const long double DINF = 1e200;
const long double PI = 3.1415926535897932384626433832795l;
int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
long long gcd(long long a, long long b) { return a ? gcd(b % a, a) : b; }
long long powmod(long long a, long long p, long long m) {
  long long r = 1;
  while (p) {
    if (p & 1) r = r * a % m;
    p >>= 1;
    a = a * a % m;
  }
  return r;
}
const int K = 50;
const int N = 1010;
const int mod = INF + 7;
int dp[2][N + 1][N + 1];
int ans[N][N];
void dodp() {
  int cur = 0;
  int asdprev = 1;
  for (int n = 0; n < (N + 1); ++n) {
    for (int p = 0; p < (N + 1); ++p) {
      dp[cur][n][p] = 1;
    }
  }
  for (int k = 1; k < K; ++k) {
    swap(cur, asdprev);
    for (int p = 0; p < (N + 1); ++p) {
      dp[cur][0][p] = 0;
    }
    for (int n = 0; n < N; ++n) {
      dp[cur][n + 1][0] = 0;
      int sum = 0;
      for (int p = 0; p < N; ++p) {
        int x = n - p >= 0 ? dp[asdprev][n - p][p] : 0;
        (sum += x) %= mod;
        dp[cur][n + 1][p + 1] = (dp[cur][n][p + 1] + sum) % mod;
      }
    }
    long long f = 1;
    for (int i = 2; i <= k; ++i) {
      f = f * i % mod;
    }
    for (int n = 0; n < (N); ++n) {
      ans[k][n] = f * dp[cur][n + 1][N] % mod;
    }
  }
}
int main() {
  dodp();
  int tc;
  cin >> tc;
  for (int qqq = 0; qqq < (tc); ++qqq) {
    int n, k;
    scanf("%d%d", &n, &k);
    printf("%d\n", ans[k][n - 1]);
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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:512000000")
using namespace std;
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline string tostr(const T& x) {
  stringstream ss;
  ss << x;
  return ss.str();
}
const long double EPS = 1e-12;
const int INF = 1000 * 1000 * 1000;
const char CINF = 102;
const long long LINF = INF * 1ll * INF;
const long double DINF = 1e200;
const long double PI = 3.1415926535897932384626433832795l;
int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
long long gcd(long long a, long long b) { return a ? gcd(b % a, a) : b; }
long long powmod(long long a, long long p, long long m) {
  long long r = 1;
  while (p) {
    if (p & 1) r = r * a % m;
    p >>= 1;
    a = a * a % m;
  }
  return r;
}
const int K = 50;
const int N = 1010;
const int mod = INF + 7;
int dp[2][N + 1][N + 1];
int ans[N][N];
void dodp() {
  int cur = 0;
  int asdprev = 1;
  for (int n = 0; n < (N + 1); ++n) {
    for (int p = 0; p < (N + 1); ++p) {
      dp[cur][n][p] = 1;
    }
  }
  for (int k = 1; k < K; ++k) {
    swap(cur, asdprev);
    for (int p = 0; p < (N + 1); ++p) {
      dp[cur][0][p] = 0;
    }
    for (int n = 0; n < N; ++n) {
      dp[cur][n + 1][0] = 0;
      int sum = 0;
      for (int p = 0; p < N; ++p) {
        int x = n - p >= 0 ? dp[asdprev][n - p][p] : 0;
        (sum += x) %= mod;
        dp[cur][n + 1][p + 1] = (dp[cur][n][p + 1] + sum) % mod;
      }
    }
    long long f = 1;
    for (int i = 2; i <= k; ++i) {
      f = f * i % mod;
    }
    for (int n = 0; n < (N); ++n) {
      ans[k][n] = f * dp[cur][n + 1][N] % mod;
    }
  }
}
int main() {
  dodp();
  int tc;
  cin >> tc;
  for (int qqq = 0; qqq < (tc); ++qqq) {
    int n, k;
    scanf("%d%d", &n, &k);
    printf("%d\n", ans[k][n - 1]);
  }
  return 0;
}

```