j02002. 音阶爬格 未做

音乐教室地板铺着 $0\sim n$ 号音阶格。你站在 $0$ 号格，每一步可以向前跨 $1$ 格或 $2$ 格。走到 $n$ 号格共有多少种不同走法？答案对 $10^9+7$ 取模。

一行一个整数 $n$。

一行走法数对 $10^9+7$ 取模的结果。

• 对于 30% 的数据，$n$ $\le$ $3\times 10^3$（朴素递推/小档递归均可）。
• 对于 60% 的数据，$n$ $\le$ $10^5$。
• 对于 100% 的数据，$2\le n\le 10^6$（必须取模）。