Description

Mingming's mother came back from a business trip and brought a box of delicious and exquisite chocolates for Mingming (the box contains a total of N pieces of chocolate, where 0 < N < 20). Mom told Mingming that he can eat one or two pieces of chocolate each day.

Assuming Mingming eats chocolate every day, how many different ways are there for Mingming to finish all the chocolates? For example:

• If N = 1, Mingming eats it on the first day, so there is 1 way.
• If N = 2, Mingming can eat 1 piece on the first day and 1 piece on the second day, or eat 2 pieces on the first day, so there are 2 ways.
• If N = 3, Mingming can eat 1 piece on the first day (leaving 2 pieces) or 2 pieces on the first day (leaving 1 piece), so there are 2 + 1 = 3 ways.
• If N = 4, Mingming can eat 1 piece on the first day (leaving 3 pieces) or 2 pieces on the first day (leaving 2 pieces), so there are 3 + 2 = 5 ways.

Now, given N, write a program to calculate the number of ways Mingming can eat all the chocolates.

Input Format

The input consists of a single line containing the integer N.

Output Format

The output consists of a single line, the number of ways Mingming can eat the chocolates.

4

5