Fast Division

Time limit2sMemory limit512 MB

Summary

Given n, let p be the smallest prime above a power tower of n twos (p(0)=2); output the remainder when the repunit with p-1 ones is divided by p.

Level: Medium7 of 10
Topics: Number theory, Math, Implementation, Brute force
Solved: No attempts yet

Problem

Ikuta loves fast programs. Lately he has been trying to make a division program fast. But it just will not get fast, so he decided to make it fast only for inputs that are "typical by common sense." The problem Ikuta is trying to solve is as follows.

For a given nonnegative integer $n$ , find the remainder when the positive integer $11...1$ with $p(n) - 1$ digits in decimal is divided by $p(n)$ . Here $p(n)$ is the smallest prime greater than $2^{2^{^{.^{.^{.^{2}}}}}}$ (with $n$ twos). Let $p(0) = 2$ .

Your job is to finish a program faster than Ikuta.

Input

The input is given in the following format.

$n$

The nonnegative integer $n$ of the problem input is given.

Output

Output the solution to the problem on one line.

Constraints

Each variable in the input satisfies the following constraint.

$0 \leq n < 1000$

Examples3

Example 1
Input
```
0
```
Expected output
```
1
```
Example 2
Input
```
1
```
Expected output
```
2
```
Example 3
Input
```
2
```
Expected output
```
1
```