ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Timus Top Coders: Third Challenge

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Lemon Tale

Time limit: 1.0 second
Memory limit: 64 MB


For each programmer a point comes when the last contest is lost, and it is time to retire. Even Three Programmers themselves could not escape the common lot. But the Programmers also wanted to keep a good memory about themselves. For this noble purpose they created problems and organized extremely popular programming contests from time to time. Of course, this work was not well paid, but for true programmers a glory was more important than money.
However it is only the first half of a job to think out a brilliant problem. The second one is to create a politically correct statement for it.


The matter is the statement of some problem for the upcoming contest was written by the Third Programmer, who knew nothing about political correctness. He just wrote a story about citrus plants growing. As a result a word "lemon" was mentioned N times in the statement.
Besides, the problem is to be looked through by famous censor Alexander K. right before the contest. And it is a known fact, that lemons remind him of oranges he hates furiously. It worries the First and the Second Programmers greatly - they know exactly, that if a word "lemon" occurs more than K times successively, the problem will be immediately disqualified from the contest.
That is why the First and the Second Programmers connived secretly to login to the server at the eve of the contest and replace some "lemons" with much more politically correct "bananas" so that the problem could not be disqualified. How many ways are there to do it?


The only line contains the integer numbers N (1 ≤ N ≤ 10000) and K (0 ≤ KN).


You should output the desired number of ways.


5 2


Let us denote a word "lemon" by a letter "L" and a word "banana" by a letter "B". So in the sample the initial sequence of words "LLLLL" might be transformed into the following politically correct sequences: "LLBLL", "LLBLB", "LLBBL", "LLBBB", "LBLLB", "LBLBL", "LBLBB", "LBBLL", "LBBLB", "LBBBL", "LBBBB", "BLLBL", "BLLBB", "BLBLL", "BLBLB", "BLBBL", "BLBBB", "BBLLB", "BBLBL", "BBLBB", "BBBLL", "BBBLB", "BBBBL" and "BBBBB".
Problem Author: Nikita Rybak, Ilya Grebnov, Dmitry Kovalioff
Problem Source: Timus Top Coders: Third Challenge
To submit the solution for this problem go to the Problem set: 1513. Lemon Tale