Sum of products#1138
Sign in

Sum of products

3 seconds
64 megabytes
Easy

Given natural numbers , , and , your task is to compute the following sum of products:

a \cdot (a + 1) \cdot \ldots \cdot (a + n - 1) + (a + 1) \cdot (a + 2) \cdot \ldots \cdot (a + n) + \ldots + b \cdot (b + 1) \cdot \ldots \cdot (b + n - 1)

Since the result can be extremely large, you need to find the remainder of this sum when divided by .

Input

The input consists of a single line containing the natural numbers , , and (a \leq b \leq 10^{18}, b - a \leq 10^7, and n \leq 10^7).

Output

Output the computed sum of products modulo .

Examples

Example 1

Loading
Loading