给定一棵具有 $n$ 个顶点的带标号有根树和一个整数 $k$。如果一个长度为 $n$ 的排列 $a$ 满足对于每个具有父节点 $par_i$ 的节点 $i$，都有 $a_i > a_{par_i}$ 且 $a_i \le a_{par_i} + k$，则称该排列为“好”的。

求好排列的数量。

现在，你认为这个问题太简单了，于是你创建了以下问题：

给定两个整数 $n, k$。对于所有不同的具有 $n$ 个顶点的带标号有根树 $T$，求 $T$ 的“拓扑问题”答案之和，对 $10^9 + 7$ 取模。

请解决“许多拓扑问题”。

当且仅当两棵带标号有根树的根节点不同，或者其中一棵树中存在某条边而另一棵树中不存在时，认为这两棵树是不同的。

输入格式

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

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

输出格式

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

样例

输入格式 1

3
2 2
5 1
114514 1919

输出格式 1

2
120
354463397