A tower has n bells; bell i rings every i minutes, and all of them ring together at minute 0. The next time all ring together is the least common multiple of 1, 2, ..., n. That number is astronomically large, so return it modulo 1_000_000_007.
Examples
Input: n = 6
Output: 60
Input: n = 1
Output: 1
Constraints
1 <= n <= 10**6- Target complexity: O(n log log n); folding lcm over 1..n with big integers is far too slow.
Goals
- Express lcm(1..n) as a product of prime powers
- Find, for each prime, the largest power not exceeding n
- Combine a sieve with modular multiplication