시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB35242472.727%

문제

Farmer John wants to position N (1 <= N <= 100,000) cows and bulls in a single row to present at the annual fair.

FJ has observed that the bulls have been quite pugnacious lately; if two bulls too close together in the line, they will argue and begin to fight, ruining the presentation. Ever resourceful, FJ calculated that any two bulls must have at least K (0 <= K < N) cows between them in order to avoid a fight.

FJ would like you to help him by counting the number of possible sequences of N bulls and cows that avoid any fighting. FJ considers all bulls the to be the same and all cows to be the same; thus, two sequences are only different if they have different kinds of cattle in some position.

입력

  • Line 1: Two space-separated integers: N and K

 

출력

  • Line 1: A single integer representing the number of ways FJ could create such a sequence of cattle. Since this number can be quite large, output the result modulo 5,000,011.

 

예제 입력 1

4 2

예제 출력 1

6

힌트

The following are the six possible sequences FJ could create (note that 'C' stands for cow and 'B' stands for bull):

CCCC
BCCC
CBCC
CCBC
CCCB
BCCB