Problem Description

A certain mathematician devised the following problem:

• A pair of rabbits produces one new pair of rabbits every month starting from the second month after birth.
• Rabbits never die.
• Under these conditions, how many pairs of rabbits will there be after one year, starting with just one pair of newborn rabbits?

※Pair: A male and a female pair

This problem is based on the above problem.
Now, suppose there is one pair of newborn rabbits.
Assuming the rabbits multiply under the same conditions as above, how many pairs of rabbits will there be after \( n \) months?
In this case, pairs of rabbits born exactly \( n \) months later should also be included in the count.

The input is given from the standard input in the following format: > \( n \)

• An integer \( n \) (\( 0 \leq n \leq 45 \)) representing the number of months is given in one line.

Output the number of rabbit pairs after \( n \) months in one line to the standard output.
A newline is required at the end of the line.

Input Format

None

Output Format

None

Sample Input and Output

Sample Input #1

0

Sample Output #1

1

Sample Input #2

5

Sample Output #2

8

Sample Input #3

45

Sample Output #3

1836311903

Notes/Hints

Sample 2:

After 2 months, there is 1 pair, after 3 months, there is 1 pair,
after 4 months, there are 2 pairs, after 5 months, 3 pairs are born,
combined with the initial 1 pair, totaling 8 pairs.

见题面 Input 部分

见题面 Output 部分