MOD = 10 ** 9 + 7

class Solution:
    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        if a > b:
            a, b = b, a

        gcd_ = gcd(a, b)
        if gcd_ > 1:
            return (gcd_ * self.nthMagicalNumber(n, a // gcd_, b // gcd_)) % MOD

        def get_idx(m: int) -> int:
            b_div = (m * a) // b
            shared = m // b
            return m + b_div - shared

        def get_next(m: int) -> int:
            b_div = (m * a) // b
            ans = min(m * a + a, b_div * b + b)
            assert ans > m * a
            return ans

        s, e, = 1, n + 1
        while s < e:
            m = (s + e) // 2
            idx = get_idx(m)
            if idx == n:
                return (m * a) % MOD
            if idx + 1 == n:
                return get_next(m) % MOD

            if idx < n:
                s = m + 1
            else:
                e = m