DP601 台阶跳跃方案

难度梯度：T2+｜训练重点：一维递推

题目描述

从第 0 级台阶走到第 N 级，每次可跨 1 级或 2 级。共有多少种不同的跳法？答案对 10^9+7 取模。不同跳法按跨步长度序列区分。

例如跨 1、2 与跨 2、1 是两种不同跳法；跨步之外不能停留或后退。

输入格式

输入一个整数 N。

输出格式

输出方案数对 10^9+7 取模后的结果。

样例输入

4

样例输出

5

样例说明

长度序列为 1111、112、121、211、22。

数据范围

1≤N≤10^6。

子任务

30 分：N≤30；70 分：无附加限制。