上楼梯

题目描述

有个小孩正在上楼梯，楼梯有n级台阶，小孩可以一次上1阶、2阶或3阶。实现一种方法，计算小孩可以由多少种上楼梯的方式。结果可能很大，你需要对结果模M求模，M=1e9+7。

输入

一个正整数n。

输出

上楼梯的方式数目（对M求模）。

样例

提示

对于100%的数据，n≤30。

来源

动规专题