Ranking

Time limit3sMemory limit1024 MB

Summary

Given N contestants and K, count the distinct rank lists in which Geumseong finishes exactly K-th, with tied scores sharing a rank, modulo 1e9+7.

Level: Medium6 of 10
Topics: Combinatorics, Dynamic programming, Math
Solved: No attempts yet

Problem

LG Electronics takes software seriously. Since 2012, it has held the LG Code Jam every year so that developers can test their problem-solving skills and enjoy intellectual challenges.

Developers who do well in the LG Code Jam are selected as coding experts and contribute to areas such as business problem solving and developer training.

Even a new developer can earn the expert title by showing outstanding skill.

LG Electronics will also hold the 2024 LG University Programming Contest to offer intellectual enjoyment to talented students.

Lucky Geumseong dreams of finishing $K$ th in the 2024 LG University Programming Contest. A total of $N$ people will take part in this contest.

Geumseong wants to count the number of distinct contest results that can occur if he finishes $K$ th. Two results are different if at least one participant has a different rank in the two contests.

Participants with the same score get the same rank. For example, three people can tie for 2nd place, and in that case the next rank is 5th.

Input

The first line contains the number of test cases $T$ .

Each of the following lines contains $N$ and $K$ for one test case, separated by a space.

Output

For each test case, print on one line the answer to the problem modulo $10^9+7$ .

Constraints

$1\leq T\leq 100\,000$
$1\leq K\leq N\leq 5\,000$

Examples1

Example 1
Input
```
4
4 1
4 2
4 3
4 4
```
Expected output
```
26
18
18
13
```