#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long qpow(long long x, long long k) {
  long long ans = 1, res = x % mod;
  while (k) {
    if (k & 1) ans = ans * res;
    ans %= mod;
    k >>= 1;
    res = res * res % mod;
  }
  return ans;
}
int main() {
  int kk;
  scanf("%d", &kk);
  while (kk--) {
    long long f, k;
    long long sum = 0;
    scanf("%lld%lld", &f, &k);
    for (int i = 1; i <= f; i++) {
      sum += qpow(i, k);
      sum %= mod;
    }
    printf("%lld\n", sum);
  }
}
