$$A(x)=\sum_{i=1}^{n+1} y_i \ell_{i}(x)$$

$$\ell_{i}(x_j)=[i==j]$$

$$\ell_i(x)=\prod_{j\ne i} \frac{x-x_j}{x_i-x_j}$$

$$A(x)=\sum_{i=1}^{n+1} y_i\prod_{j\ne i} \frac{x-x_j}{x_i-x_j}$$

$emmmmmmmmm$

$$\sum_{i=1}^{k+1} y_i\prod_{j\ne i} \frac{n-x_j}{x_i-x_j}$$

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define mod 1000000007
#define ll long long
#define K 50005
int T, sgn;
ll fac[K + 3], y[K + 3], inv[K + 3], ans[K], p[K], q[K];
struct ANS{
ll n;
int k, id;
friend inline bool operator < (const ANS &x, const ANS &y)
{
return x.k < y.k;
}
}t[K];
inline ll pow (ll x, int p = mod - 2)
{
ll sum = 1;
while (p)
{
if (p & 1) sum = sum * x % mod;
x = x * x % mod, p >>= 1;
}
return sum;
}
inline ll solve (ll n, int k)
{
ll ans = 0, num = n;
++k;
//  fo (i, 1, k)
//      num = num * (n - i) % mod;
sgn = k & 1 ? -1 : 1;
p[0] = n;
fo (i, 1, k) p[i] = p[i - 1] * (n - i) % mod;
q[k + 1] = 1;
fd (i, k, 1) q[i] = q[i + 1] * (n - i) % mod;
fo (i, 1, k)
{
sgn = -sgn;
ans = (ans + y[i] * fac[i] % mod * fac[k - i] % mod * p[i - 1] % mod * q[i + 1] * sgn) % mod;
}
return (ans + mod) % mod;
}
int main ()
{
scanf("%d", &T);
fac[0] = 1;
inv[1] = 1;
fo (i, 2, K) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
fo (i, 1, K) fac[i] = fac[i - 1] * inv[i] % mod;
y[0] = 0;
fo (i, 1, T)
{
scanf("%lld %d", &t[i].n, &t[i].k);
t[i].id = i;
}
std::sort(t + 1, t + T + 1);
fo (i, 1, T)
{
t[i].n = t[i].n % mod;
if (t[i - 1].k < t[i].k)
fo (j, 1, t[i].k + 1) y[j] = (y[j - 1] + pow(1LL * j, t[i].k)) % mod;
if (t[i].k + 1 >= t[i].n)
ans[t[i].id] = y[t[i].n];
else
ans[t[i].id] = solve(t[i].n, t[i].k);
}
fo (i, 1, T)
printf("%lld\n", ans[i]);
return 0;
}