No submission language available for this problem.

Background

Special for beginners, ^_^

Description

有一种有规律的数列叫做斐波那契数列：数列的第一个数和第二个数都是 1，接下来的每个数都是前两个数之和。

数列如：1 1 2 3 5 8 13 21 34 ...

现要求你输出第 t ( t <= 50) 个斐波那契数

Format

Input

一行一个整数 t

Output

输出一个整数表示第 t 个斐波那契数

Samples

1

1

3

2

13

233

Limitation

1s, 1024KiB for each test case.