Description

给出两个正整数 $n, k$。你需要计算：从 $0,1,\ldots,n-1$ 这 $n$ 个整数中随机选择 $k$ 个不同的整数，组成的集合的 $MEX$ 的期望是多少？可以证明答案为一个有理分数 $\frac{x}{y}$，你需要输出这个分数对 $10^9 + 7$ 取模后的结果。

$MEX$ 表示集合内最小的未出现的自然数，例如 $MEX(1,0,2,4)=3, MEX(1,2,3,4)=0$。

Input

第一行一个正整数 $T$ ($1 \le T \le 10^4$)，表示数据组数。

对于每一组数据，输入两个正整数 $n, k$ ($1 \le k \le n \le 10^9$)。

Output

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

Samples

5
3 2
10 7
1000 278
1000000 114514
1000000000 20250406

1
750000007
15214385
93181493
131113678

Resources

The 23rd UESTC Programming Contest Final