Nth Magical Number
A positive integer is magical if it is divisible by either a or b.
Given the three integers n, a, and b, return the n^th magical number. Since the answer may be very large, return it modulo 10^9 + 7.
Example 1
Input
n = 1, a = 2, b = 3Output
2The first positive integer divisible by either 2 or 3 is 2.
Example 2
Input
n = 4, a = 2, b = 3Output
6The magical numbers divisible by either 2 or 3 are 2, 3, 4, 6, so the 4th magical number is 6.
Constraints
- 1 <= n <= 10^9
- 2 <= a, b <= 4 * 10^4