题目描述

小海是一个快乐的少年，对于爬楼梯这种事情，他每次上楼梯的时候，要么往上跨一级，要么往上跨两级。对于有 n 级台阶的楼梯，小海想知道他从最下面走到最上面的方法总数。

输入格式

输入一个数字 n，代表台阶总数。

输出格式

输出一个整数，代表小海从最下面走到最上面的方法总数。

样例数据

input

5

output

5

数据规模与约定

1<n<=50

时间限制：$1 \text{s}$

空间限制：$256 \text{MB}$