k-MEX

Problem Description

给出两个正整数 $n, k$。你需要计算：从 $0,1,\ldots,n-1$ 这 $n$ 个整数中随机选择 $k$ 个不同的整数，组成的集合的 $MEX$ 的期望是多少？可以证明答案为一个有理分数 $\frac{x}{y}$，你需要输出这个分数对 $10^9 + 7$ 取模后的结果。 $MEX$ 表示集合内最小的未出现的自然数，例如 $MEX\left(1,0,2,4\right)=3, MEX\left(1,2,3,4\right)=0$。

Input

第一行一个正整数 $T$（$1 \le T \le 10^4 + 7$），表示数据组数。 对于每一组数据，输入两个正整数 $n, k$（$1 \le k \le n \le 10^9$）。

Output

对于每一组数据，输出一行一个整数，表示期望 $MEX$ 对 $10^9 + 7$ 取模后的结果。

Sample Input

5
3 2
10 7
1000 278
1000000 114514
1000000000 20250406

Sample Output

1
750000007
15214385
93181493
131113678

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（5）