说明

楼梯有 n 级台阶，每次可以走 1、2 或 3 级。问到达楼顶有多少种不同走法？（序列不同即为不同走法）

输入格式

一行，一个整数 n（1 \le n \le 50）。

输出格式

一行，走法总数。

4

7

提示

考虑最后一步： - 走 1 级 -> 前 n-1 级有 f(n-1) 种 - 走 2 级 -> 前 n-2 级有 f(n-2) 种 - 走 3 级 -> 前 n-3 级有 f(n-3) 种 **递推公式**：f(n) = f(n-1) + f(n-2) + f(n-3) 初始值：f(1)=1, f(2)=2, f(3)=4。C++ 用 `long long`。