You’re climbing a staircase with n stairs. On each step, you can either climb 2 stairs or climb only 1. How many different ways are there to climb those stairs?
Input
The input contains a single integer n (1 ≤ n ≤ 45).
Output
The output should contain the number of different ways you can climb those staircases.