Category

Similar Problems

0778. Task

Time limit : 1000 ms
Memory limit : 64 mb

Your task in this problem is to find the sum of integer numbers from 1 to N witch are divisible by A or B, and print the sum modulo 1000000007(109+7).

Input

On first line given numbers N, A, B(1≤N,A,B≤1018).

Output

Print required sum modulo 1000000007.

Samples

Input

Output

1

7 2 3

15

Note

Numbers, divisible by 2: 2, 4, 6. Numbers, divisible by 3: 3, 6.

Sum of these numbers: 2 + 3 + 4 + 6 = 15

 

Tayyorladi: Azat Yusupov