분수는 연분수일 때 더 좋다

면접 대비

시간 제한1초메모리 제한1024 MB

요약

정수 N이 주어질 때, p_0 = 1이고 p_N = 1 / (1 + p_(N-1))로 정의된 분수 p_N을 기약분수로 나타낸 분자를 출력합니다.

문제

리틀 찰스는 세계 최고의 경쟁 프로그래머 중 한 명이었다. 하지만 그는 프로그래밍을 그리 좋아하지 않았다. 이제 은퇴한 그는 진짜 좋아하는 연분수 연구에 전념할 수 있다.

곧 열리는 Imensa Competição de Phrações Contínuas (ICPC)에 대비해, 그는 다음 문제를 풀어야 한다.

$p_0 = 1$ 을 레벨 0 분수로 정의한다. 이어서 $p_1 = \frac{1}{1+1}$ 을 레벨 1 분수 $p_1$ 로, $p_2 = \frac{1}{1 + \frac{1}{1+1}}$ 을 레벨 2 분수 $p_2$ 로 정의하며, 같은 방식으로 계속 정의한다.

정수 $N$ 이 주어졌을 때, 분수 $p_N$ 의 분자 값을 구하는 문제이다.

첫 번째이자 유일한 줄에 정수 $N$ ( $1 \le N \le 40$ )이 주어진다.

$p_N$ 은 서로소인 $\frac{a}{b}$ 꼴로 나타낼 수 있다. $a$ 의 값을 한 줄에 출력한다.