Many Topological Problems

Once you created the following problem:

**Topological Problem**

You are given a labeled rooted tree with $n$ vertices and an integer $k$. We call a permutation $a$ of length $n$ good if $a_i>a_{par_i}$ and $a_i\le a_{par_i}+k$ for each $i$ with a parent $par_i$.

Find the number of good permutations.

Now, thinking this problem is too easy, you create the following problem:

**Many Topological Problems**

You are given two integers $n,k$. For all different labeled rooted trees $T$ with $n$ vertices, find the sum of the answer to the *Topological Problem* of $T$, modulo $10^9+7$.

Please solve **Many Topological Problems**.

Two labeled rooted trees are considered different, if and only if their roots differ, or one edge exists in one tree but not in the other.

The first line contains a single integer $T$ ($1\le T\le 10$), denoting the number of test cases.

For each test case, the only line contains two integers $n,k$ ($1\le k\le n\le 10^6$).

For each test case, output one line with an integer denoting the answer.

3
2 2
5 1
114514 1919

2
120
354463397

2023“钉耙编程”中国大学生算法设计超级联赛（10）