Staircase

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.

Examples

Input	Output
2	2
3	3

Explanation

For 2 stairs → (1) 1 step + 1 step. (2) 2 steps

For 3 stairs → (1) 1 step + 1 step + 1 step. (2) 1 step + 2 steps. (3) 2 steps + 1 step

Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB