AU7_5  STUDENTS
Problem Statement
Professor X wants to position N (1 <= N <= 100,000) girls and boys in a single row to present at the annual fair.
Professor has observed that the boys have been quite pugnacious lately; if two boys too close together in the line, they will argue and begin to fight, ruining the presentation. Ever resourceful, Professor calculated that any two boys must have at least K (0 <= K < N) girls between them in order to avoid a fight.
Professor would like you to help him by counting the number of possible sequences of N boys and girls that avoid any fighting. Professor considers all boys to be the same and all girls to be the same; thus, two sequences are only different if they have different kinds of students in some position.
Input
First line contains C (1<=C<=20) the number of test cases
Next C lines contain N and K
Output
A single integer representing the number of ways Professor could create such a sequence of students. Since this number can be quite large, output the result modulo 5000011.
Sample Input
1
4 2
Sample Output
6
Explanation
GGGG
BGGG
GBGG
GGBG
GGGB
BGGB
Time Limit
1s
hide comments
Rishav Goyal:
20140607 15:19:57
learnt something new :) 

Man Mohan Mishra:
20130531 13:32:05
awesome problem !!


fitcat:
20130531 06:20:15
My 500th completed classical problem :) 
Added by:  arun 
Date:  20130508 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: BF 