You're climbing a staircase with n steps. With each move you can climb either 1 or 2 steps.
Return the number of distinct ways to reach the top.
Examples
Example 1
- Input
- n = 2
- Output
- 2
- Why
- 1 step + 1 step, or 2 steps at once.
Example 2
- Input
- n = 3
- Output
- 3
- Why
- 1 + 1 + 1, 1 + 2, or 2 + 1.
Constraints
1 <= n <= 45