Background

Special for beginners, ^_^

Description

斐波那切数列 $0,1,1,2,3,5,8,13,21,34,55\dots$ 从第三项起，每一项都是紧挨着的前两项的和。写出计算斐波那切数列的任意一个数据项递归程序。

Format

Input

输入所求的项数。

Output

输出数据项的值。

Samples

9

34

Limitation

1s, 1024KiB for each test case.

所有数据均在 int 范围之内。