Climbing Stairs

You are climbing a staircase with n steps. Each time you can either climb 1 or 2 steps. Return the number of distinct ways you can climb to the top.

Example

Input: n = 2 → Output: 2 Explanation: Two ways: (1 step + 1 step) or (2 steps).

Input: n = 3 → Output: 3 Explanation: Three ways: (1+1+1), (1+2), (2+1).

Input: n = 5 → Output: 8

Constraints

• 1 ≤ n ≤ 45