LCM of 1 through n

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

Medium5Number theoryMathNo attempts yetTime limit2sMemory limit256 MB

Description

Examples7

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}$ .