Road Shop

Time limit1sMemory limit128 MB

Summary

Count the number of ways to choose bead counts for n colors summing to r, with at least m beads of each color.

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

Problem

Having lost interest in computer science, Sang-geun opened a road shop whose flagship product is bead necklaces. He has an unlimited supply of beads in $n$ different colors. He wants to make a necklace of exactly $r$ beads, using at least $m$ beads of every one of the $n$ colors. Two necklaces are counted as different kinds only when the combination of how many beads of each color they use differs (the order or arrangement of the beads is not distinguished). How many different kinds of necklaces can Sang-geun make?

Input

The first line contains three integers $n$ , $m$ , and $r$ , separated by spaces.

Output

Print the number of different kinds of necklaces that can be made.

Constraints

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

Examples3

Example 1
Input
```
2 0 3
```
Expected output
```
4
```
Example 2
Input
```
3 1 4
```
Expected output
```
3
```
Example 3
Input
```
4 2 5
```
Expected output
```
0
```