310. Hippopotamus
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard
After fixing your roof, you still think that it looks unpretty. So you opt for a new one, consisting of
n consecutive long narrow boards. You have two types of boards: wooden ones and iron ones, giving you an amazing total of 2
n possible roofs.
But the safety should not be left aside. Having considered the weight and the cruising speed of a falling hippopotamus, you decide to have at least
k iron boards among every
m consecutive boards.
How many possibilities do you have?
Input
The input file contains three integers,
n,
m and
k, separated by spaces and/or line breaks. 1 ≤
n ≤ 60, 1 ≤
m ≤ 15, 0 ≤
k ≤
m ≤
n.
Output
Output the number of possibilities.
Example(s)
sample input | sample output |
10 2 1
|
144
|
sample input | sample output |
5 5 2
|
26
|
sample input | sample output |
3 2 2
|
1
|