Sequences

Interview

Time limit2sMemory limit512 MB

Summary

Count non-decreasing length-n sequences over 1 to m where each integer appears at most k times. Use DP over the largest value and its count.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

Write a program that counts the non-decreasing sequences of length n containing integers from 1 to m, where each element appears at most k times.

Input

The standard input contains the integers n, m, and k, separated by spaces.

Output

The standard output must contain the number of sequences that meet the conditions.

Constraints

0 < n < 31
0 < m < 31
0 < k < 31

Hint

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).

Examples1

Example 1
Input
```
3 4 2
```
Expected output
```
16
```