题目描述

上楼的楼梯一共有 $n$ 个台阶，可以一次上一个台阶，也可以一次上两个台阶，还可以一次上三个台阶。问一共有多少种不同的上楼方法。

输入格式

一个正整数 $n$。

输出格式

上楼的方法数。

输入输出样例

4

7

60

4680045560037375

说明/提示

👀️ 对于$100\%$的数据，$n \leq 70$。