로드샵

시간 제한1초메모리 제한128 MB

요약

n가지 색의 구슬 개수가 합이 r이 되고 각 색을 최소 m개씩 사용하도록 고르는 경우의 수를 구한다.

난이도: 보통10점 중 4점
유형: 조합론, 수학, 동적 계획법
정답자: 아직 제출이 없습니다

문제

상근이는 로드샵을 열고 구슬 목걸이를 판다. 상근이네 집에는 구슬이 무한히 많으며, 색은 모두 $n$ 가지이다. 목걸이 하나는 구슬 $r$ 개로 만들고, $n$ 가지 색을 각각 $m$ 개 이상 사용해야 한다. 두 목걸이는 각 색을 사용한 개수의 조합이 다를 때에만 서로 다른 종류로 센다(구슬을 늘어놓는 순서나 배치는 구분하지 않는다). 상근이가 만들 수 있는 목걸이는 모두 몇 종류인가?

입력

첫째 줄에 세 정수 $n$ , $m$ , $r$ 이 공백으로 구분되어 주어진다.

출력

만들 수 있는 목걸이의 종류의 수를 첫째 줄에 출력한다.

제한

$0 \le m < n \le r \le 10000$

예제3

예제 1
입력
```
2 0 3
```
예상 출력
```
4
```
예제 2
입력
```
3 1 4
```
예상 출력
```
3
```
예제 3
입력
```
4 2 5
```
예상 출력
```
0
```