You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一楼梯共 $n$ 级，若每次只能跨上一级或者二级，要走上 $n$ 级，共有多少不同走法？ 给定一个正整数 $n$ ，请返回一个数，代表上楼的方式数。

数据保证 $n$ 小于等于 $70$。

输入格式

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

输出格式

一个整数，表示方案数量

样例

样例一

输入

1

输出

1

样例二

输入

7

输出

21

数据范围与提示

$n \le 70$