#200HardMath & Number Theory· Binary Search with Inclusion-Exclusion

Nth Festival Bell Ring

A festival has two bells. The first rings every `a` minutes (at minutes `a, 2a, 3a, ...`) and the second every `b` minutes (at minutes `b, 2b, 3b, ...`). When both bells ring at the same minute, the organisers hear it as a single ring. Return the minute at which the `n`-th ring is heard, counting from the first ring. The answer can be very large, so return it modulo `1,000,000,007`.

Input format

`n`: which ring to find; `a` and `b`: the intervals of the two bells in minutes.

Output format

An integer: the minute of the n-th ring modulo 1000000007.

Examples

Input: n = 3, a = 2, b = 3

Output: 4

The rings happen at minutes 2, 3, 4, 6, ... so the third ring is at minute 4.

Input: n = 4, a = 2, b = 3

Output: 6

The fourth ring is at minute 6, when both bells ring together and count as one ring.

Input: n = 1, a = 2, b = 3

Output: 2

The first ring is at minute 2.

Constraints

1 <= n <= 10^9
2 <= a, b <= 4 * 10^4

#math
#number-theory
#binary-search
#gcd
#inclusion-exclusion