Background

Special for beginners, ^_^

Description

所谓斐波那契数列是指，第1个数为1，第2个数为1，从第3个数开始，每个数为前两个数之和，比如第3个数为1+1=2，第4个数为1+2=3……现在请你输出斐波那契数列，第N个数是多少？

Format

Input

第一行，一个整数N(N<=50),表示求数列中第N个数

Output

一行，一个整数，表示数列中第N个数

Samples

5

5

Limitation

1s, 1024KiB for each test case.