题目背景

跳台阶的题目不陌生，类似于斐波那契数列，使用递归或者递推求解。

题目描述

楼梯有n个台阶，一次可以跳上1 , 2 或3 阶，那么总共有多少种方法可以上完n阶台阶呢？

输入格式

一个正整数n，表示有n个台阶。

输出格式

一个数字，表示方法数量，由于结果很大，要输出对1,000,000,007取余的结果。

样例

4

7

30

53798080

100

347873931

数据范围

对于60%的数据：$n\le30$。

对于100%的数据：$n\le1000$。

提示

使用普通的递归可以获得60分，但对于100%的数据会超时，你需要加一些手段，或者直接使用递推。