Background

Special for beginners, ^_^

Description

斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21……从第三项开始每一项是前两项的和。 现在输入一个数n，需要求斐波纳契数列第n项的值。

Format

Input

一个正整数n

Output

一个整数为斐波纳契数列第n项的值

Samples

6

8

Limitation