P73162

跳楼梯

难度 3 级 小学 动态规划入门 递推
讨论 统计 2通过 18提交 11.1%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

OpportunityFan(以下简称OF)正在准备体育考试,他为跳远感到忧愁。VHOS建议他每天跳N级台阶,锻炼爆发力。为此,OF给自己制订了一项规则:

当他跳到偶数台阶时,他可以跳2级或3级;

当他跳到奇数台阶时,他可以跳1级或4级。

请问,若刚开始时他处在0级(属于偶数),他跳到N级的方案数是多少?

输入

一行一个整数,表示N。

输出

一行一个整数,表示跳到N级的方案数。最后的结果对(10^9+7取模

样例

样例 1
输入
9
输出
4

提示

n \leq 5× 10^ 7

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交