题目描述

颁皮的小朋友发现，下楼梯时每步可以走 1 个台阶、2 个台阶或 3 个台阶。现在一共有 N 个台阶，你能帮小朋友算算有多少种方案吗？

输入格式

输入一行，包含一个整数 N。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1

4

输出 #1

7

输入 #2

10

输出 #2

274

说明/提示

对于全部的测试点，保证 1 <= N <= 60。