题目描述

小达正在上楼梯，楼梯有n阶台阶，小达一次可以上1阶、2阶或3阶。请你计算小达有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

输入格式

输入一个正整数n（ n ≤1e6），代表台阶数

输出格式

输出一个整数，为方案数模1000000007的结果

3

4

5

13