LCM of 1 through n

Time limit2sMemory limit256 MB

Summary

Compute the least common multiple of all integers from 1 to n (n up to 10^8) and print it modulo 2^32.

Level: Medium5 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

Given a natural number $n$ , write a program that computes the least common multiple of every natural number from $1$ to $n$ .

Input

The first line contains $n$ ( $2 \le n \le 10^8$ ).

Output

Print the least common multiple of every natural number that is at least $1$ and at most $n$ . The answer can be very large, so print it modulo $2^{32}$ .

Examples7

Example 1
Input
```
2
```
Expected output
```
2
```
Example 2
Input
```
5
```
Expected output
```
60
```
Example 3
Input
```
10
```
Expected output
```
2520
```
Example 4
Input
```
1000
```
Expected output
```
2495707648
```
Example 5
Input
```
9876
```
Expected output
```
2149851136
```
Example 6
Input
```
10203040
```
Expected output
```
427819008
```
Example 7
Input
```
20151204
```
Expected output
```
1023410176
```