784 . 小明上樓梯

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

dnda
Burn chicken everyday...

User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

45.5% (15/33)

Tags

apcsc apcsc-dp

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
Submit
Back to Top