题目描述

楼梯有$n$个台阶，智智想上$n$个台阶，但是他有一想法:

• 当他站在编号为偶数的台阶，接下来的一步可以上1个台阶，也可以上2个台阶。
• 当他站在编号为奇数的台阶，接下来一步他可以上1个台阶，也可以上3个台阶。

一共有多少种上楼的方法？一开始他在0号台阶。

输入格式

一个整数$n$ ，表示$n$个台阶。

输出格式

输出一个整数表示上楼的方案数。

样例

3

2

5

6

数据范围

$n \le 50$