AU7_5 - STUDENTS

no tags 

 

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: 2014-06-07 15:19:57

learnt something new :)

Man Mohan Mishra: 2013-05-31 13:32:05

awesome problem !!
got AC after trying for some more cases :)

fitcat: 2013-05-31 06:20:15

My 500th completed classical problem :)


Added by:arun
Date:2013-05-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF