1228 序列求和 (伯努利数)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
const int N = 2005;
typedef long long ll;
const ll mod = 1e9 + 7;
ll inv[maxn], b[maxn], fac[maxn];
ll fiv[maxn];
ll qpow(ll a, ll b) {
  ll ans = 1;
  while (b) {
    if (b & 1) {
      ans = (ans * a) % mod;
    }
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans % mod;
}
ll C(ll n, ll m) {
  return fac[n] * fiv[m] % mod * fiv[n - m] % mod;
}
int main() {
  b[0] = 1; inv[1] = 1, fac[0] = 1,fiv[0] = 1;
  for (int i = 2; i <= N; i++) {
    inv[i] = (mod - mod / i) * inv[mod % i] % mod;
  }
  for (int i = 1; i <= N; i++) {
    fac[i] = fac[i - 1] * i % mod;
    fiv[i] = qpow(fac[i], mod - 2);
  }
  for (int i = 1; i <= N; i++) {
    ll sum = 0;
    for (int j = 0; j < i; j++) {
      sum = (sum + C(i + 1, j) * b[j]) % mod;
    }
    b[i] = -inv[i + 1] * sum;
    b[i] = (b[i] % mod + mod) % mod;
  }
  ll T, n, k;
  cin >> T;
  while (T--) {
    cin >> n >> k;
    ll p = (n + 1) % mod; ll mul = p;
    ll ans = 0;
    for (int i = 1; i <= k + 1; i++) {
      ans = (ans + C(k + 1, i) * b[k + 1 - i] % mod * mul % mod) % mod;
      mul = mul * p % mod;
    }
    cout << ans * inv[k + 1] % mod << endl;
  }
  return 0;
}