Background背景

斐波那契数列又称黄金分割数列，指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89...

现在请你求出斐波那契数列中的第k个数是多少。

Input输入

输入一行，包含一个正整数 k。（1≤k≤46）

Output输出

输出一行，包含一个正整数，表示斐波那契数列中的第k个数。

Samples样例

6

8

19

4181

Limitation限制

1s, 1024KiB for each test case.