Given integers n, a, b, and c, return the n-th positive integer that is divisible by at least one of a, b, or c. Because the answer can be large, return it modulo 10^9 + 7.
Input
n: 1-indexed position in the sequence of ugly numbers
a: positive divisor
b: positive divisor
c: positive divisor
Output
The n-th ugly number modulo 10^9 + 7.
Examples
Example 1
Inputn = 10, a = 2, b = 3, c = 5
Output14
Explanation: The first 10 ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10, 12, 14.
Example 2
Inputn = 2, a = 3, b = 4, c = 5
Output4
Constraints
n >= 1; a, b, c are positive integers.
Return the answer modulo 10^9 + 7.