Climbing Stairs

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

Two sequences of moves are considered different if the order of 1-steps and 2-steps differs.

Example 1

Input: n = 2
Output: 2
Explanation: (1 step, 1 step) or (2 steps).

Example 2

Input: n = 4
Output: 5
Explanation: (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2)

Constraints

• 1 <= n <= 45