Description

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

Format

Input

输入一个数字N，N<=45

Output

如题

Samples

6

5