#include <bits/stdc++.h>
using namespace std;
template <class T>
ostream& operator<<(ostream& os, vector<T> V) {
  os << "[ ";
  for (auto v : V) os << v << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, set<T> S) {
  os << "{ ";
  for (auto s : S) os << s << " ";
  return os << "}";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
template <class L, class R>
ostream& operator<<(ostream& os, map<L, R> M) {
  os << "{ ";
  for (auto m : M) os << "(" << m.F << ":" << m.S << ")";
  return os << "}";
}
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
const int N = 1005;
const int mod = 1e9 + 7;
int dp[2][N][N];
inline int add(int a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
inline int mul(int a, int b) { return a * 1ll * b % mod; }
const int T = 2e5 + 100;
int solve[T];
vector<pair<int, int> > query[N];
int fac[2 * N], inv[2 * N];
int power(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = mul(res, a);
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}
int nCr(int n, int r) {
  if (r > n || n < 0) return 0;
  return mul(fac[n], mul(inv[r], inv[n - r]));
}
void sole(int k) {
  for (auto it : query[k]) {
    int n = it.first;
    int ans = 0;
    for (int sum = 0; sum <= n; ++sum) {
      ans = add(ans, mul(nCr(n - sum, k), mul(fac[k], dp[0][sum][N - 1])));
    }
    solve[it.second] = ans;
  }
}
void pre() {
  fac[0] = 1;
  inv[0] = 1;
  for (int i = 1; i < 2 * N; ++i) {
    fac[i] = mul(fac[i - 1], i);
    inv[i] = power(fac[i], mod - 2);
  }
  for (int i = 0; i < N; ++i) {
    for (int j = i; j < N; ++j) dp[0][i][j] = 1;
  }
  sole(1);
  for (int no = 2; no < 50; ++no) {
    for (int sum = 0; sum < N; ++sum) {
      for (int upp = 0; upp < N; ++upp) {
        int& x = dp[1][sum][upp];
        if (upp <= sum && upp) x = add(x, dp[0][sum - upp][upp - 1]);
        if (upp) x = add(x, dp[1][sum][upp - 1]);
      }
    }
    for (int sum = 0; sum < N; ++sum) {
      for (int upp = 0; upp < N; ++upp) {
        dp[0][sum][upp] = dp[1][sum][upp];
        dp[1][sum][upp] = 0;
      }
    }
    sole(no);
  }
  for (int no = 50; no < N; ++no) {
    for (auto it : query[no]) solve[it.second] = 0;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << fixed << setprecision(25);
  int t;
  cin >> t;
  for (int z = 1; z <= t; ++z) {
    int n, k;
    cin >> n >> k;
    query[k].push_back(make_pair(n, z));
  }
  pre();
  for (int i = 1; i <= t; ++i) cout << solve[i] << "\n";
  return 0;
}

### Prompt

Please formulate 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;
template <class T>
ostream& operator<<(ostream& os, vector<T> V) {
  os << "[ ";
  for (auto v : V) os << v << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, set<T> S) {
  os << "{ ";
  for (auto s : S) os << s << " ";
  return os << "}";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
template <class L, class R>
ostream& operator<<(ostream& os, map<L, R> M) {
  os << "{ ";
  for (auto m : M) os << "(" << m.F << ":" << m.S << ")";
  return os << "}";
}
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
const int N = 1005;
const int mod = 1e9 + 7;
int dp[2][N][N];
inline int add(int a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
inline int mul(int a, int b) { return a * 1ll * b % mod; }
const int T = 2e5 + 100;
int solve[T];
vector<pair<int, int> > query[N];
int fac[2 * N], inv[2 * N];
int power(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = mul(res, a);
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}
int nCr(int n, int r) {
  if (r > n || n < 0) return 0;
  return mul(fac[n], mul(inv[r], inv[n - r]));
}
void sole(int k) {
  for (auto it : query[k]) {
    int n = it.first;
    int ans = 0;
    for (int sum = 0; sum <= n; ++sum) {
      ans = add(ans, mul(nCr(n - sum, k), mul(fac[k], dp[0][sum][N - 1])));
    }
    solve[it.second] = ans;
  }
}
void pre() {
  fac[0] = 1;
  inv[0] = 1;
  for (int i = 1; i < 2 * N; ++i) {
    fac[i] = mul(fac[i - 1], i);
    inv[i] = power(fac[i], mod - 2);
  }
  for (int i = 0; i < N; ++i) {
    for (int j = i; j < N; ++j) dp[0][i][j] = 1;
  }
  sole(1);
  for (int no = 2; no < 50; ++no) {
    for (int sum = 0; sum < N; ++sum) {
      for (int upp = 0; upp < N; ++upp) {
        int& x = dp[1][sum][upp];
        if (upp <= sum && upp) x = add(x, dp[0][sum - upp][upp - 1]);
        if (upp) x = add(x, dp[1][sum][upp - 1]);
      }
    }
    for (int sum = 0; sum < N; ++sum) {
      for (int upp = 0; upp < N; ++upp) {
        dp[0][sum][upp] = dp[1][sum][upp];
        dp[1][sum][upp] = 0;
      }
    }
    sole(no);
  }
  for (int no = 50; no < N; ++no) {
    for (auto it : query[no]) solve[it.second] = 0;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << fixed << setprecision(25);
  int t;
  cin >> t;
  for (int z = 1; z <= t; ++z) {
    int n, k;
    cin >> n >> k;
    query[k].push_back(make_pair(n, z));
  }
  pre();
  for (int i = 1; i <= t; ++i) cout << solve[i] << "\n";
  return 0;
}

```