빠른 나눗셈

시간 제한2초메모리 제한512 MB

요약

2를 n번 쌓은 탑보다 큰 가장 작은 소수 p(p(0)=2)에 대해, 1이 p-1개 늘어선 수를 p로 나눈 나머지를 구한다.

난이도: 보통10점 중 7점
유형: 정수론, 수학, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

이쿠타 군은 빠른 프로그램을 매우 좋아한다. 최근에는 나눗셈 프로그램을 빠르게 만들려고 한다. 그러나 좀처럼 빨라지지 않아서, "상식적으로 생각했을 때 전형적인" 입력에 대해서만 빠르게 만들면 된다고 생각했다. 이쿠타 군이 풀려고 하는 문제는 다음과 같다.

주어진 음이 아닌 정수 $n$ 에 대해, 10진법으로 $p(n) - 1$ 자리인 양의 정수 $11...1$ 을 $p(n)$ 으로 나눈 나머지를 구하라. 단, $p(n)$ 은 $2^{2^{^{.^{.^{.^{2}}}}}}$ (2가 $n$ 개)보다 큰 최소의 소수를 나타낸다고 한다. $p(0) = 2$ 로 둔다.

당신의 일은 이쿠타 군보다 빠르게 프로그램을 완성하는 것이다.

입력

입력은 다음 형식으로 주어진다.

$n$

문제의 입력인 음이 아닌 정수 $n$ 이 주어진다.

출력

문제의 해를 1줄에 출력하라.

제한

입력 중 각 변수는 다음 제약을 만족한다.

$0 \leq n < 1000$

예제3

예제 1
입력
```
0
```
예상 출력
```
1
```
예제 2
입력
```
1
```
예상 출력
```
2
```
예제 3
입력
```
2
```
예상 출력
```
1
```