Problem Description

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.

Input

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$).

Output

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

3
2 2
5 1
114514 1919

2
120
354463397