Climbing Stairs

Beacon Hill Museum has a single staircase to the upper gallery, and the visitor guide wants a fun fact printed beside it: how many different ways a visitor could get to the top. A visitor moves up either one stair or two at a time, in any mixture, until they arrive exactly at the top. Two visits count as different when the sequence of moves differs, so going one-then-two is not the same visit as going two-then-one.

Task: Print how many different sequences of moves reach the top.

Input

A single line holding one integer: the number of stairs, between 1 and 45.

Output

One line holding a single integer: the count of distinct move sequences that land exactly on the top stair. Each move goes up one stair or two, never more, and never past the top. Two sequences using the same moves in a different order count as two.

Example:

Input:
5

Output:
8