爬樓梯的走法數

題目敘述

學校的教學大樓有一座 n 階的樓梯。每一步可以跨 1 階或 2 階，直到剛好踏上最後一階。兩種步伐的先後順序不同就算不同走法，請算出總共有幾種走法。

輸入格式

• 第 1 行：整數 n，表示階數。
• 第 2 行：n 個整數。這一行只是為了統一輸入格式而存在，不會影響答案。

輸出格式

輸出一個整數：不同走法的總數，對 1000000007 取模。

限制

• 1 ≤ n ≤ 10⁶
• 第 2 行的 n 個整數，在評測資料中的範圍是 [0, 5]

範例

範例 1

輸入

2
0 0

輸出

2

說明

兩階的樓梯有兩種走法：1+1 或 2。

範例 2

輸入

3
0 0 0

輸出

3

說明

三階的樓梯有三種走法：1+1+1、1+2、2+1。注意 1+2 與 2+1 是不同的走法。

範例 3

輸入

1
0

輸出

1

說明

只有一階時，只能跨一小步，所以只有一種走法。

範例 4

輸入

5
0 0 0 0 0

輸出

8

說明

n = 0, 1, 2, 3, 4, 5 的答案依序是 1, 1, 2, 3, 5, 8。

範例 5

輸入

1
2

輸出

1

範例 6

輸入

5
1 2 3 4 5

輸出

8

說明

• n 最大到 10⁶，把每一種走法逐一列出來會來不及。