#include <bits/stdc++.h>
using namespace std;
template <class T>
void debug(T a, T b) {
  ;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
namespace std {
template <class S, class T>
ostream& operator<<(ostream& out, const pair<S, T>& a) {
  out << '(' << a.first << ',' << a.second << ')';
  return out;
}
}  // namespace std
const int mod = 1000000007;
struct Int {
  unsigned x;
  int mpow(Int a, int k) {
    Int res = 1;
    while (k) {
      if (k & 1) res = res * a;
      a = a * a;
      k >>= 1;
    }
    return res.x;
  }
  int inverse(Int a) { return mpow(a, mod - 2); }
  Int() : x(0) {}
  Int(long long sig) {
    int sigt = sig % mod;
    if (sigt < 0) sigt += mod;
    x = sigt;
  }
  int get() const { return (int)x; }
  Int& operator+=(Int that) {
    if ((x += that.x) >= mod) x -= mod;
    return *this;
  }
  Int& operator-=(Int that) {
    if ((x += mod - that.x) >= mod) x -= mod;
    return *this;
  }
  Int& operator*=(Int that) {
    x = (unsigned long long)x * that.x % mod;
    return *this;
  }
  Int& operator=(Int that) {
    x = that.x;
    return *this;
  }
  Int& operator/=(Int that) {
    x = (unsigned long long)x * inverse(that.x) % mod;
    return *this;
  }
  bool operator==(Int that) { return x == that.x; }
  bool operator>(Int that) { return x > that.x; }
  bool operator<(Int that) { return x < that.x; }
  Int operator+(Int that) const { return Int(*this) += that; }
  Int operator-(Int that) const { return Int(*this) -= that; }
  Int operator*(Int that) const { return Int(*this) *= that; }
  Int operator/(Int that) const { return Int(*this) /= that; }
};
namespace std {
ostream& operator<<(ostream& out, const Int& a) {
  out << a.get();
  return out;
}
istream& operator>>(istream& in, Int& a) {
  in >> a.x;
  return in;
}
};  // namespace std
Int dp[55][1005];
Int ans[55][1005];
Int way[55][1005];
Int fact[1005];
Int C[1505][1505];
int main() {
  for (int i = 0; i < (1500); ++i) {
    C[i][0] = 1;
    for (int j = 0; j < (i); ++j) C[i][j + 1] = C[i - 1][j + 1] + C[i - 1][j];
  }
  fact[0] = 1;
  for (int i = 0; i < (1000); ++i) fact[i + 1] = fact[i] * (i + 1);
  for (int k = 1; k <= 50; ++k) {
    memset((dp), 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 0; i < (k); ++i)
      for (int j = 0; j < (1001); ++j)
        if (dp[i][j] > 0) {
          if (i == 0 && j == 0) dp[i + 1][j] += dp[i][j];
          if (j + (k - i) <= 1000) dp[i + 1][j + (k - i)] += dp[i][j];
          if (j + (k - i) <= 1000) dp[i][j + (k - i)] += dp[i][j];
        }
    for (int j = 0; j < (1001); ++j) way[k][j] = dp[k][j];
  }
  for (int k = 1; k <= 50; ++k)
    for (int n = k; n <= 1000; ++n) {
      if (k * (k + 1) / 2 > n)
        ans[k][n] = 0;
      else {
        for (int i = k * (k - 1) / 2; i <= n - k; ++i) {
          Int tmp = way[k][i] * fact[k];
          int rest = n - i - k;
          if (rest >= 0) {
            tmp *= C[rest + k][k];
            ans[k][n] += tmp;
          }
        }
      }
    }
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, k;
    scanf("%d%d", &n, &k);
    Int res = 0;
    if (k * (k + 1) / 2 > n)
      ;
    else
      res = ans[k][n];
    printf("%d\n", res.get());
  }
  return 0;
}

### Prompt

Please create a solution in Cpp 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;
template <class T>
void debug(T a, T b) {
  ;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
namespace std {
template <class S, class T>
ostream& operator<<(ostream& out, const pair<S, T>& a) {
  out << '(' << a.first << ',' << a.second << ')';
  return out;
}
}  // namespace std
const int mod = 1000000007;
struct Int {
  unsigned x;
  int mpow(Int a, int k) {
    Int res = 1;
    while (k) {
      if (k & 1) res = res * a;
      a = a * a;
      k >>= 1;
    }
    return res.x;
  }
  int inverse(Int a) { return mpow(a, mod - 2); }
  Int() : x(0) {}
  Int(long long sig) {
    int sigt = sig % mod;
    if (sigt < 0) sigt += mod;
    x = sigt;
  }
  int get() const { return (int)x; }
  Int& operator+=(Int that) {
    if ((x += that.x) >= mod) x -= mod;
    return *this;
  }
  Int& operator-=(Int that) {
    if ((x += mod - that.x) >= mod) x -= mod;
    return *this;
  }
  Int& operator*=(Int that) {
    x = (unsigned long long)x * that.x % mod;
    return *this;
  }
  Int& operator=(Int that) {
    x = that.x;
    return *this;
  }
  Int& operator/=(Int that) {
    x = (unsigned long long)x * inverse(that.x) % mod;
    return *this;
  }
  bool operator==(Int that) { return x == that.x; }
  bool operator>(Int that) { return x > that.x; }
  bool operator<(Int that) { return x < that.x; }
  Int operator+(Int that) const { return Int(*this) += that; }
  Int operator-(Int that) const { return Int(*this) -= that; }
  Int operator*(Int that) const { return Int(*this) *= that; }
  Int operator/(Int that) const { return Int(*this) /= that; }
};
namespace std {
ostream& operator<<(ostream& out, const Int& a) {
  out << a.get();
  return out;
}
istream& operator>>(istream& in, Int& a) {
  in >> a.x;
  return in;
}
};  // namespace std
Int dp[55][1005];
Int ans[55][1005];
Int way[55][1005];
Int fact[1005];
Int C[1505][1505];
int main() {
  for (int i = 0; i < (1500); ++i) {
    C[i][0] = 1;
    for (int j = 0; j < (i); ++j) C[i][j + 1] = C[i - 1][j + 1] + C[i - 1][j];
  }
  fact[0] = 1;
  for (int i = 0; i < (1000); ++i) fact[i + 1] = fact[i] * (i + 1);
  for (int k = 1; k <= 50; ++k) {
    memset((dp), 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 0; i < (k); ++i)
      for (int j = 0; j < (1001); ++j)
        if (dp[i][j] > 0) {
          if (i == 0 && j == 0) dp[i + 1][j] += dp[i][j];
          if (j + (k - i) <= 1000) dp[i + 1][j + (k - i)] += dp[i][j];
          if (j + (k - i) <= 1000) dp[i][j + (k - i)] += dp[i][j];
        }
    for (int j = 0; j < (1001); ++j) way[k][j] = dp[k][j];
  }
  for (int k = 1; k <= 50; ++k)
    for (int n = k; n <= 1000; ++n) {
      if (k * (k + 1) / 2 > n)
        ans[k][n] = 0;
      else {
        for (int i = k * (k - 1) / 2; i <= n - k; ++i) {
          Int tmp = way[k][i] * fact[k];
          int rest = n - i - k;
          if (rest >= 0) {
            tmp *= C[rest + k][k];
            ans[k][n] += tmp;
          }
        }
      }
    }
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, k;
    scanf("%d%d", &n, &k);
    Int res = 0;
    if (k * (k + 1) / 2 > n)
      ;
    else
      res = ans[k][n];
    printf("%d\n", res.get());
  }
  return 0;
}

```