问题 C: 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 ��>�����ai>apari and ��≤�����+�ai≤apari+k for each $i$ with a parent ����pari.

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 109+7109+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≤�≤�≤1061≤k≤n≤106).

3
2 2
5 1
114514 1919

2
120
354463397