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

Example 1:

Input:  2
Output: 2

(1+1, 2)

Example 2:

Input:  3
Output: 3

(1+1+1, 1+2, 2+1)

Constraints:

• 1 ≤ n ≤ 45

Input format: A single integer n.

Output format: Number of distinct ways.