Nth Magical Number

Try to solve the Nth Magical Number problem.

We'll cover the following

Statement

Given three integers n, a, and b, return the nth magical number.

A magical number is defined as a positive integer that is divisible by either a or b.

As the result may be very large, return it modulo 109+710^9+7.

Constraints:

  • 1≤1 \leq n ≤109\leq 10^9

  • 2≤2 \leq a, b ≤4×104\leq 4 \times 10^4

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.