TopCoder

dnda
Burn chicken everyday...

User's AC Ratio

100.0% (17/17)

Submission's AC Ratio

48.6% (18/37)

Tags

Description

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

Input Format

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

  • 1N5×106

Output Format

一次可以爬一階或兩階,有幾種方式爬上這樓梯,請輸出答案除以 109+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