Task#5227

Task

1 second
128 megabytes
Hard

Watson set a simple task for Rybka: to find the sum of all integers less than that are divisible by or , and print this sum modulo (10^9 + 7). Help Rybka solve this task.

Input

The input consists of a single line containing three integers , , and .

1 \leq N, A, B < 10^{18}.

Output

Print the required sum modulo .

Examples

Example 1

Loading
Loading