4455 - 跳楼梯
时间限制 : 1 秒
内存限制 : 128 MB
OpportunityFan(以下简称OF)正在准备体育考试，他为跳远感到忧愁。VHOS建议他每天跳N级台阶，锻炼爆发力。为此，OF给自己制订了一项规则:
当他跳到偶数台阶时，他可以跳2级或3级;
当他跳到奇数台阶时，他可以跳1级或4级。
请问，若刚开始时他处在0级(属于偶数),他跳到N级的方案数是多少?
输入
一行一个整数，表示N。
输出
一行一个整数，表示跳到N级的方案数。最后的结果对(10^9+7取模
样例
输入
9
输出
4
提示
n \leq 5× 10^ 7
来源
VHOS