Loading...
Loading...
Loading...
Ananya's hostel room is at the top of a staircase with n steps. She is in a hurry, so on every move she goes up either 1 step or 2 steps.
Two ways are different when their lists of moves are different. For example, 1 then 2 is not the same as 2 then 1. Print how many different ways she can reach the top, the n-th step.
The count grows very fast, so print it modulo 10^9 + 7 (the remainder after dividing by 1000000007).
Example 1
Input
4
Output
5
The five ways are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.
Example 2
Input
5
Output
8
Eight ways: the five ways to reach step 4 plus one more step, and the three ways to reach step 3 plus a 2-step move.
Try the problem first. Open one hint at a time.
Think about the very last move. Ananya reaches step i either from step i - 1 or from step i - 2.
So the number of ways to reach step i is the ways to reach step i - 1 plus the ways to reach step i - 2.
Start the table with one way to stand at step 0 (do nothing) and one way to reach step 1.
Take the remainder after every addition so the numbers stay small.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor