All Tracks Math Combinatorics Inclusion-Exclusion Problem

Candy Distribution

Math, Medium


Raj is a Maths teacher at \(XYZ\) Public School. He admires students who pay attention in class and is very strict to the undisciplined ones. Himanshu is the most sincere student of his class while Dev is the most undisciplined one.

XYZ Public School is celebrating Teacher's Day today. So, Raj needs to distribute candies in his class. Unfortunately all the students except Himanshu and Dev are busy in celebration. Raj has N candies with him. He will distribute them among Himanshu and Dev. Since Raj admires Himanshu, he will give Himanshu strictly more candies than Dev. Raj gives X candies to Himanshu and Y candies to Dev. (X>Y and X+Y=N). The distribution process is a bit weird. Raj doesn't give all the candies at once. He distributes them one at a time.

Suppose he has 3 candies and he gave 2 to Himanshu and 1 to Dev, the possible distributions are:

1. 1st candy to Himanshu, 2nd to Dev, 3rd to Himanshu.

2. 1st to Himanshu, 2nd to Himanshu, 3rd to Dev.

3. 1st to Dev, 2nd to Himanshu and 3rd to Himanshu.

So in total there are 3 possible distributions.

Raj wants to know in how many such distributions, Himanshu has strictly more candies than Dev throughout the distribution.

So let us examine the previous example. The candy distribution at each step are:

We will assume H denotes Himanshu and D denotes Dev.

Distribution 1:- After 1st candy (H-1, D-0), after 2nd candy (H-1,D-1), after 3rd candy (H-2,D-1). So we see that after second candy H doesn't have greater candy than D so this distribution is not valid for Raj.

Distribution 2: After 1st candy (H-1,D-0), after 2nd candy (H-2,D-0),after 3rd candy (H-2,D-1). So this is a valid distribution as H always have greater candy than D.

Distribution 3: After 1st candy (H-0,D-1), after 2nd candy (H-1,D-1), after 3rd candy (H-2.D-1). This is again not a valid distribution because of (H-0,D-1).

So we have only 1 valid distribution.

Since the number of such distributions could be huge output them modulo \(10^9+7.\)

Input :

The First line contains an integer T denoting the number of test cases. Then we have T lines. Each line contains 3 space separated integers. N, X, Y that are the total number of candy, number of candy Himanshu gets and number of candy Dev gets respectively.


For each test case output the total number of valid distributions.

Constraints :

1 <= T <= \(10^3\)

1 <= N, <= \(10^6\)

0 <= Y < X <= N

3 2 1
5 4 1

Input 1 is the one explained above.

Input 2: Following are the valid distributions


Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

January Easy '17

View All Notifications