You climb a staircase of n steps, taking 1 or 2 steps at a time. How many distinct ways are there to reach the top?

Input: one integer n (1 ≤ n ≤ 45). Output: the number of ways.

Your program reads from stdin and prints to stdout.