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$ 项。

Format

Input

一行，一个整数 $n$ 。

Output

一个整数，表示第 $n$ 项斐波那契数。

Samples

5

5

Hints

1,1,2,3,5,8...
其中，第五项为5。

Limitation

$1 \le n \le 42$