该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

假设有三种上楼梯的步伐：1个台阶/步，2个台阶/步、3个台阶/步，每当走了一步3个台阶后，下一步就只能走一步1个台阶。从1楼到2楼有n级台阶。有多少种不同的走法。
输入一行，一个整数n，n<30，表示台阶数。
输出一行，一个整数，表示不同走法的个数。

输入样例1：

4

输出样例1：

7

输入样例2：

5

输出样例2：

12