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 \leq 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 \leq T \leq 10)$, denoting the number of test cases.

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

Output

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

Example

3
2 2
5 1
114514 1919

2
120
354463397