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 .