The Lucky Letter

Time limit2sMemory limit512 MB

Summary

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

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

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 $m$ . Find the smallest positive integer $n$ such that $n \equiv a-1 \pmod{a}$ for every natural number $a$ with $2 \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 $n$ whose remainder on division by $a$ equals $a-1$ for every integer $a$ with $2 \le a \le m$ .

Input

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

Output

Print the smallest positive integer $n$ that satisfies the condition. When $m$ is $1000$ , $n$ has $433$ digits, so it does not fit in a 64-bit integer type.

Examples4

Example 1
Input
```
2
```
Expected output
```
1
```
Example 2
Input
```
3
```
Expected output
```
5
```
Example 3
Input
```
4
```
Expected output
```
11
```
Example 4
Input
```
5
```
Expected output
```
59
```