Universal Divisibility Challenge

One day, szb met Grey Wolf on his way to school. Grey Wolf said, "Help us solve this problem and we will let you go." The challenge was stated as follows: Given an integer n, find the smallest positive number that is divisible by every integer in the range \([1, n]\), and output the answer modulo \(100000007\).

This problem tests your understanding of the least common multiple (LCM) and basic number theory. In order to solve it, you may need to iteratively compute the LCM of numbers from 1 to n using the relationship:

[ \text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)} ]

Remember to apply the modulo operation only at the final step (after computing the LCM) to avoid issues with division under modulo arithmetic.

inputFormat

The input consists of a single integer n (1 ≤ n), representing the upper bound of the range [1, n].

outputFormat

Output a single integer: the smallest number that is divisible by every number from 1 to n, taken modulo 100000007.

sample

1

1