ID: 119

Type: Default

1000ms

256MiB

Difficulty: 3

Uploaded By:

Tags>

递推

数组

Description

给出一个数 $n$ ，请求出斐波那契数列的第 $n$ 项。

Format

Input

一行，一个整数 $n$ 。

Output

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

Samples

Hints

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

Limitation

$1 \le n \le 70$