Description

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

Input

一个整数N，N<=1000。

Output

共有多少种走法。

Sample Input

10

Sample Output

274

HINT

Source

NBU OJ