Ugly Number III
Write a program to find the n
-th ugly number.
Ugly numbers are positive numbers that are divisible by either a
, b
, or c
.
Since the number can be too large, return the actual answer modulo 10^9 + 7
Example 1:
Input:n = 10
, a = 2
, b = 3
, c = 5
Output: 14
Explanation: 2, 3, 4, 5, 6, 8, 9, 10, 12, 14
is the sequence of the first 10
ugly numbers.
Example 2:
Input:n = 2
, a = 3
, b = 4
, c = 5
Output: 4
Explanation: 3, 4
is the sequence of the first 2
ugly numbers.
Constraints
1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18