- All Contests
- HourRank 21
- Sam's Numbers

# Sam's Numbers

# Sam's Numbers

Once, Sam started to write down numbers in a row. Let's call this list .

Each number was between and , inclusive, and the *absolute difference* between any adjacent pair of numbers was at most , i.e., for all . As soon as she stopped writing, she noticed that the sum of the numbers she wrote was .

For example, if , and , then she could have written the list . Notice that each number is between and , inclusive, the absolute difference between any adjacent pair is , and the sum is .

She then started thinking how many different ways this could have happened, i.e., how many lists of numbers satisfy all the conditions above. Can you help her in calculating this number?

As the answer can be very large, apply a modulo on the result before printing it.

**Input Format**

The first and only line of input contains three space-separated integers denoting , and respectively.

**Constraints**

**Subtasks**

- For of the maximum score,
- For of the maximum score,

**Output Format**

Print a single line containing a single integer denoting the requested number modulo .

**Sample Input 0**

```
4 3 1
```

**Sample Output 0**

```
5
```

**Explanation 0**

There are such lists:

- ]

Notice that

- The sum of the numbers in each list is .
- Each value is between and , inclusive.
- The absolute difference between any two adjacent pairs is .