Muhammad al-Xorazmiy nomidagi TATU Urganch filiali talabalari o'rtasida musobaqa , I tur
Contest Problems
Problem Tasks
# | Date | State |
---|
Not Contest
# | Date | State |
---|
H. 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