Limits 1s, 512 MB

“Among us!” game which became popular in this year. The game is usually played with 6-10 players where players are divided into two groups. Those are impostors (1-3 player) and crew mates(7-9) divided randomly. No one knows which player is an impostor except those who are in the impostors groups. The job of an impostor is to kill the crew mates and reduce the number of crew mates equal to the living impostors. The crew mates will try to find out who is the impostor among them with available clues and kill the impostor. To learn more about the game you can read this. (Though this is not necessary for this problem.)

Impostors win the game if the number of living impostors and crew mates become equal. Crew mates win the game if there are no impostors left.(For simplicity there is no task in the game but only killing between each other :P)

You are given total number of the player who started this game N and the number of impostors M which will be randomly selected from among N. Find out the number of possible combinations where the impostors won the game.

As the answer may be big, print the result modulo 109 + 7 .

Input

The first line contains T - the number of test case (1 ≤ T ≤ 105).

Next T Lines contains two integer N(2 ≤ N ≤ 106) , M(M ≤ N/2 ) .

It is guaranteed that the sum of M over all test case does not exceed 106

Output

Output T Lines — ”Total number of possible combinations where the impostors won the game".

Sample

InputOutput
2
5 1
10 5
20
63252

Test Case 1: There are total 5 players and 1 imposter among them. There are total 5 different way to select imposter among 5 players and total 4 different ways to select wining condition for imposters group. So the answer is 20.


Submit

Login to submit.

Statistics

81% Solution Ratio
akash740Earliest, Dec '20
nusuBotFastest, 0.0s
shreasLightest, 5.1 MB
MursaleenShortest, 616B
Toph uses cookies. By continuing you agree to our Cookie Policy.