当前没有测试数据。

Description

小赛同学在放暑假的时候特别无聊，想找一找他一共有多少下楼梯的办法。 已知，在下楼梯的时候，小赛一次只能下1或者2阶楼梯。

请问在从N阶楼梯上下来一共有多少种方法？

Format

Input

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

Output

输出一行，包含一个正整数，表示下这N阶楼梯有多少种方式。

Samples

【输入样例1】

2

【输出样例1】

2

【输入样例2】

19

【输出样例2】

4181

Hint

样例1： 一共2阶楼梯，两种方法分别为：从0先到1，再到2阶，另一种为直接走到2阶。