Consider a set, $\mbox{S}$, consisting of $\boldsymbol{\mbox{k}}$ integers. The set is beautiful if at least one of the following conditions holds true for every $x\in S$:

$x-1\in S$
$x+1\in S$

For example, $S=\{1,2,50,51\}$ is beautiful but $S=\{1,5,9\}$ is not beautiful. Given two integers, $n$ and $\boldsymbol{\mbox{k}}$, can you find the number of different $\boldsymbol{\mbox{k}}$-element beautiful sets you can create using integers $\in[1,n]$?

Perform $\textit{q}$ queries where each query $\boldsymbol{i}$ consists of some $n_i$ and $k_i$. For each query:

Find the number of different beautiful sets having exactly $\boldsymbol{\mbox{k}}$ elements that can be generated using integers in the inclusive range from $1$ to $n$.
Print the number of beautiful sets, modulo $10^9+7$, on a new line.

Input Format

The first line contains an integer, $\textit{q}$, denoting the number of queries.

Each line $\boldsymbol{i}$ of the $\textit{q}$ subsequent lines consists of two space-separated positive integers describing the respective values of $n_i$ and $k_i$ for the query.

Constraints

$1\leq q\leq10$
$1\leq n\leq10^{6}$
$1\leq k\leq n$

Subtasks

$1\leq n\leq1000$ for $\textbf{40\%}$ of the maximum score.

Output Format

For each query, print the number of different beautiful sets of size $\boldsymbol{\mbox{k}}$ that can be generated using integers in the inclusive range from $1$ to $n$ on a new line. As the answers to these queries can be quite large, each answer must be modulo $10^9+7$.

Sample Input
2
6 4
27 2

Sample Output
6
26

Explanation

For the first query, the beautiful sets of size $k=4$ we can create using numbers from $1$ to $n=6$ are shown below:

$\{1,2,3,4\}$
$\{2,3,4,5\}$
$\{3,4,5,6\}$
$\{1,2,4,5\}$
$\{1,2,5,6\}$
$\{2,3,5,6\}$

As there are are six such sets, we print the result of $6\%(10^9+7)=6$ on a new line.

见题面

见题面