一二级台阶

难度：T4

【知识点：从暴力递归建立DP状态】

前置知识：从暴力递归建立DP状态及其冻结前置单元。

题目描述与输入

输入$n$，每次向前走$1$或$2$级，恰好到达$n$。

输出

输出走法数对$1000000007$取模。

数据范围

$0$<=$n<=2000$；落点费用绝对值<=$10^6$。

样例输入

4

样例输出

5

样例说明

按最后一步划分到达方式，状态是恰好到位置$i$。请按输入操作顺序逐步核对；没有规定输出的更新操作不输出额外内容。