Competitions

Sequences

Count the number of all non-decreasing sequences of length n containing integers from 1 to m, where every element can occur at most k times.

Input

Three integers n, m and k (0 < n, m, k < 31).

Output

Print the number of described sequences.

Example

The sequences are: (1,1,2), (1,1,3), (1,1,4), (1,2,2), (1,2,3), (1,2,4), (1,3,3), (1,3,4), (1,4,4), (2,2,3), (2,2,4), (2,3,3), (2,3,4), (2,4,4), (3,3,4), (3,4,4).

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 4 2

Output example #1
16

Source 2017 IX International autumn tournament in informatics, Shumen, Junior, Day 1, Problem A