题目描述

在一个古老的城堡中，有一座神秘的楼梯，它通向顶层的宝藏房间。楼梯共有 $n$ 级台阶，每次你可以选择走一级台阶，或者跳跃两级台阶。现在，冒险家小k站在楼梯的第 $0$ 级台阶，准备开始他的挑战，他的目标是到达第 $n$ 级台阶。

然而，楼梯上有许多隐藏的陷阱，只有通过正确的步伐才能安全到达终点。你能帮助小k计算，从第 $0$ 级台阶走到第 $n$ 级台阶，一共有多少种不同的走法吗？

输入格式

共一行，包含一个整数 $n$，表示楼梯的级数。

输出格式

共一行，输出一个整数，表示小k从第 $0$ 级台阶到第 $n$ 级台阶的所有不同走法总数。

数据范围 $1\leq n\leq 15$

样例

5

8