递归版台阶问题升级

题目描述

小鹿上楼梯，一步可以迈 $1$ 个、$2$ 个或 $3$ 个台阶，现共有 $n$ 个台阶。请编写递归程序计算小鹿上到第 $n$ 个台阶共有几种走法。

递归转换公式：$\text{step}(n)=\text{step}(n-1)+\text{step}(n-2)+\text{step}(n-3)$（$n\ge 4$）； 递归出口：$\text{step}(1)=1,\ \text{step}(2)=2,\ \text{step}(3)=4$。

输入格式

一行，一个整数 $n$，表示台阶数量（$1 < n < 20$）。

输出格式

一行，一个整数，表示上到第 $n$ 个台阶的总走法数。

样例

4

7

5

13

说明/提示

对于所有测试点，保证 $1 < n < 20$。