Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

I'm Impostor

By ssohan · 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 .


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 T Lines — ”Total number of possible combinations where the impostors won the game".


5 1
10 5

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.



    79% Solution Ratio

    akash740Earliest, 1M ago

    riyad000Fastest, 0.0s

    shreasLightest, 5.1 MB

    MursaleenShortest, 616B


    Login to submit