House Robber

Climbing Stairs

easy

Time: O(n)

Space: O(1)

You are climbing a staircase. It takes n steps to reach the top. Each time you can climb 1 or 2 steps. In how many distinct ways can you reach the top?

Constraints

1 <= n <= 45

Examples

Input: n = 2

Output: 2

1+1, 2

Input: n = 3

Output: 3

1+1+1, 1+2, 2+1