시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

Write program sequences to 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.

입력

On the standard input, there are given integers n, m and k, separated by spaces.

출력

On the standard output, your program has to print the count of the described sequences. 

제한

  • 0 < n < 31
  • 0 < m < 31
  • 0 < k < 31.

예제 입력 1

3 4 2

예제 출력 1

16

힌트

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