The Lucky Letter

Find the smallest positive n whose remainder modulo every a from 2 to m equals a-1, that is, n ≡ -1 mod each a.

Medium4Number theoryMathNo attempts yetTime limit2sMemory limit512 MB

Problem

Jigui got this letter one day.

This letter began in England, travelled around the world once a year, and brought luck to everyone who received it. Now it has reached you. You must solve the problem below within 12 hours and send seven copies of this letter, this one included, to people who need luck. Copying is allowed. (...) The number written on this letter is mm. Find the smallest positive integer nn such that na1(moda)n \equiv a-1 \pmod{a} for every natural number aa with 2am2 \le a \le m.

Jigui read the letter all the way to the end by accident and has felt uneasy ever since, because the problem is still unsolved. Solve it for Jigui.

Put another way, find the smallest positive integer nn whose remainder on division by aa equals a1a-1 for every integer aa with 2am2 \le a \le m.

Input

The first line contains the integer mm written on the letter. (2m10002 \le m \le 1000)

Output

Print the smallest positive integer nn that satisfies the condition. When mm is 10001000, nn has 433433 digits, so it does not fit in a 64-bit integer type.