‹ 上一题下一题 ›

07359. 跨一或三阶未做

1000 ms 256 MB 测试点 10 通过率 50% 线性DP

文件读写输入07359.in输出07359.out

题目描述

每次可以跨 $1$ 级或 $3$ 级（不能跨 $2$ 级）。走到第 $n$ 级有多少种走法？ $f_{0} = 1$ 。

输入格式

一行一个整数 $n$ 。

输出格式

一行一个整数：走法数。

样例

输入

输出

数据范围

$1 \leq n \leq 90$ 。

输入

输出

答案