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

  1. For 2 stairs β†’ (1) 1 step + 1 step. (2) 2 steps
  1. For 3 stairs β†’ (1) 1 step + 1 step + 1 step. (2) 1 step + 2 steps. (3) 2 steps + 1 step
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue