Problem Statement

Given the three integers n, a, and b, return the n^th magical number modulo 10^9 + 7 as it can be very large.

A positive integer is called magical if it is divisible by either a or b.

Examples

• Example 1:

  • Input: n = 3, a = 2, b = 3
  • Expected Output: 4
  • Justification: The first three magical numbers divisible by 2 or 3 are 2, 3, and 4. The third magical number is 4.

• Example 2:

  • Input: n = 5, a = 3, b = 4
  • Expected Output: 9
  • Justification: The sequence of magical numbers that are divisible by 3 or 4 begins as 3, 4, 6, 8, 9. The fifth one in this sequence is 9.

• Example 3:

  • Input: n = 20, a = 3, b = 5
  • Expected Output: 42
  • Justification: The 20^th magical number for a = 30, and b = 5 is 42.

Try it yourself

Try solving this question here: