All Tracks Math Combinatorics Inclusion-Exclusion Problem

Candy Distribution
Tag(s):

Math, Medium

Problem
Editorial
Analytics

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. $$1$$st candy to Himanshu, $$2$$nd to Dev, $$3$$rd to Himanshu.

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

3. $$1$$st to Dev, $$2$$nd to Himanshu and $$3$$rd 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.

Output:

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

Constraints :

$$1$$ <= T <= $$10^3$$

$$1$$ <= N, <= $$10^6$$

$$0$$ <= Y < X <= $$N$$

SAMPLE INPUT
2
3 2 1
5 4 1
SAMPLE OUTPUT
1
3
Explanation

Input 1 is the one explained above.

Input 2: Following are the valid distributions

HHDHH, HHHDH, HHHHD

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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

January Easy '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications