许多拓扑问题

中文题目为机翻，原题目请参考英文题面

有一次你创建了下面的问题

给你一棵有 $n$ 顶点和一个整数 $k$ 的带标签有根树。如果 $a_i > a_{par_i}$ ，并且 $a_i \leq a_{par_i} +k$ 且每个 $i$ 都有一个父序列 $par_i$ ，我们称长度为 $n$ 的排列组合 $a$ 为好排列组合。

求好的排列数。

现在，您觉得这个问题太简单了，于是又提出了下面的问题：

给你两个整数 $n,k$ 。对于顶点为 $n$ 的所有不同标签的有根树 $T$ ，求 $T$ 的 拓扑问题 答案之和，模数为 $10^9 + 7$ 。

请解决多拓扑问题。

当且仅当两棵树的根不同，或者一条边存在于一棵树中而不存在于另一棵树中时，这两棵有标注根的树被认为是不同的。

输入

第一行包含一个整数 $T \: (1 \leq T \leq 10)$ ，表示测试用例的数量。

对于每个测试用例，唯一一行包含两个整数 $n,k \: (1 \leq k \leq n \leq 10^6)$ .

对于每个测试用例，输出一行，用一个整数表示答案。

3
2 2
5 1
114514 1919

2
120
354463397