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

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

输入格式

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

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

输出格式

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

样例

输入

5
3 2
10 7
1000 278
1000000 114514
1000000000 20250406

输出

1
750000007
15214385
93181493
131113678