Background

Special for beginners, ^_^

Rabbit Breeding

Problem Description

There is a kind of rabbit. One month after birth it grows up; in the second month it becomes an adult rabbit; then in the third month, one pair of grown-up rabbits can give birth to one pair of baby rabbits, and from then on they can give birth to one pair every month. Now we have one pair of just-born rabbits of this kind. After $n$ months, how many pairs of rabbits will we have, assuming no rabbit ever dies?

Input Format

One line containing a natural number $n$ ($1 \le n \le 46$).

Output Format

One line containing a natural number: the number of pairs of rabbits after $n$ months.

Sample Input

5

Sample Output

5

Constraints

1s, 1024KiB for each test case.