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

## CODE EDITOR

Initializing Code Editor...