All Tracks Math Combinatorics Basics of Combinatorics Problem

Bob and Internship
Tag(s):

Easy

Problem
Editorial
Analytics

Bob got selected for N day long internship in which he is required to complete M tasks . Each task can be completed in exactly one day . As Bob is very lazy he needs atleat K days for rest before starting any new task . In how many ways you can complete these M tasks. It does not matter in which order you complete these M tasks . Also it is not necessary to take rest after the last task . As output can be very large you have to print answer Modulo \(10^{9}+7\) .

NOTE : Two ways  \(D_1,D_2,........,D_M\) and  \(D_1^{'},D_2^{'},........,D_M^{'}\)are considered diferent if for any \(1 \leq i \leq M\)   \( D_i \neq D_i^{'} \) . 


INPUT 

FIrst line of input contains T number of test cases

Next T lines contains three space seperated integers N , M , K .


OUTPUT

For each test case print the number of ways in which Bob can complete these M tasks in new line .


CONSTRAINTS

\(1 \leq T \leq 10^6\)

\(1 \leq M \leq N \leq 10^6\)

\(0 \leq K \leq 10^6\)

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

Test Case 1 : There are 4 days in which we have to complete 2 tasks . So possible combinations in which we can complete tasks are  \([1,3] , [1,4] , [2,4]\).

You can see we are taking rest of minimum 1 day between two tasks.

Test Case 2 :  There is only one possible way \([1,4]\) as we have to maintain two day gap between them . 

Time Limit: 0.5 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: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, 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

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?