1115. Climbing Stairs

You are climbing a staircase with n steps. Each time you may climb either 1 or 2 steps. Return the number of distinct ways to reach the top. The input is JSON {n}.

Input: JSON {n}.

Output: Integer — the number of distinct ways.

Examples

Input: {"n":2}
Output: 2
Explanation: 1+1 or 2.

Input: {"n":3}
Output: 3
Explanation: 1+1+1, 1+2, or 2+1.

Input: {"n":1}
Output: 1
Explanation: One way.

Constraints

• 0<=n<=45

Asked by