You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

输入一个正整数 n，输出斐波那契数列的第 n 项（数列从1开始：第1项=1，第2项=1，第3项=2，依此类推）。

1 1 2 3 5 8 ……

Format

Input

One integer n, satisfying $1\leq n\leq 30$

Output

One integer

Samples

5

5

Limitation

$1\leq n\leq 30$