该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

你们有一个神人学长，做到了走楼梯不走台阶，能用他的 “无CD八向喷气”（过程中创飞一个同学直接结束CD）下楼。 但是很明显你不能，所以你还是要正常下楼。
亮亮：“这样下楼太没意思了，咱不如求一下我一共能用多少种方法下楼吧。”
同学：“你无不无聊……”
因为亮亮学长得不到答复，只好来求助你了。

题目描述

学校下楼的台阶共$n$级，亮亮学长每次可以选择向下迈$i$级台阶，其中$1\le i\le 3$ 问亮亮学长走下这$n$级台阶有多少种方案 因为数据过大，输出结果为方案数$\%1e10+7$

输入格式

一个正整数$n$

输出格式

一个正整数，为方案数$\%10^{10}+7$的结果

样例

3

4

数据范围

• $1\le n\le 3\times10^8$（谁家好人学校这么多台阶）