题目描述

王老师爬楼梯，他可以每次走1级或者2级或者3级楼梯，输入楼梯的级数，求不同的走法数。（要求递推求解）如果N很大，需要高精度计算。

输入要求

一个整数N，N<=1000。

输出要求

共有多少种走法。

输入样例

10

输出样例

274

提示

来源

NBU OJ