Step Ways
Time: 1.0 s Memory: 1024 MB
-
You are walking down the stairs of your office, since you walk up and down every day you have counted there to be exactly $N$ steps. When you walk down the stairs you can either take one step or two steps at a time. Bored as you are and to keep your mind occupied, you realize there are many ways to walk down the stairs. If you have 4 steps you can walk down the stairs in the following ways:
-
1-1-1-1
-
1-2-1
-
2-1-1
-
1-1-2
-
2-2
How many ways are there to walk down the stairs if you have $N$ steps?
Input
The first and only line of the input contains an integer $N$ ($1 \le N \le 100000$).
Output
Output the number of ways to walk down the stairs modulo $10^9 + 7$.
Sample Input 1 Sample Output 1 4
5
Sample Input 2 Sample Output 2 100
782204094
-
-
To solve the problems, you can either start a virtual contest or register for regular practice. A virtual contest simulates a participation in the original contest with a duration of 1 day, while regular practice lets you submit solutions without any constraints.
You must log in to register. - A Mincost Walk
- B Step Ways