Staircase
You’re climbing a staircase with
n stairs. On each step, you can either climb 2 stairs or climb only 1. How many different ways are there to climb those stairs?Input
The input contains a single integer
n (1 ≤ n ≤ 45).Output
The output should contain the number of different ways you can climb those staircases.
Examples
Input | Output |
2 | 2 |
3 | 3 |
Explanation
- For 2 stairs → (1) 1 step + 1 step. (2) 2 steps
- For 3 stairs → (1) 1 step + 1 step + 1 step. (2) 1 step + 2 steps. (3) 2 steps + 1 step
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB