Climbing Stairs

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? This is essentially Fibonacci: ways(n) = ways(n-1) + ways(n-2) Example: n=3 → 3 ways: 1+1+1, 1+2, 2+1

Input

A single integer n.

Output

The number of distinct ways to climb.

Sample

3

Expected

3