TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

60.0% (3/5)

Tags

Description

小明已經厭倦了在數學課本中生活了,他決定去外面的世界闖一闖。出現在他面前的,是一座有 $N$ 階的樓梯。小明突然意識到他一次可以爬一階或兩階,「不…不行…我已經不是以前的我了……但我真的好想算我能用幾種方式爬上這樓梯…」,看來他老毛病又復發了,請你大發慈悲幫他算一下他可以用幾種不同方式爬上樓梯。

Input Format

一個整數 $N$ 代表樓梯有幾階。

  • $1 \le N \le 5 \times 10^ 6$

Output Format

一次可以爬一階或兩階,有幾種方式爬上這樓梯,請輸出答案除以 $10^ 9+7$ 的餘數。

Sample Input 1

2

Sample Output 1

2

Sample Input 2

5

Sample Output 2

8

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~12 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2