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 2n 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?
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 the number of possibilities.
10 2 1
5 5 2
3 2 2
Codeforces (c) Copyright 2010-2021 Mike Mirzayanov