class Solution {
public:
    const int MOD = 1e9+7;
    typedef long long ll;
    int nthMagicalNumber(int n, int a, int b) {
        ll l = min(a,b);
        ll r = (ll)n*l;
        int  c = lcm(a,b);

        while(l <= r)
        {
            ll mid = (l+r)>>1;
            ll cnt = mid/a+mid/b-mid/c;
            if(cnt >= n)
            r = mid - 1;
            else
            l = mid + 1;
        }

        return (r + 1) % MOD;
    }
};