Two zeros in a binary number

In the binary numeral system, consider a number with n digits. The first and last digits of this number are both ones. Additionally, between any two ones, there can be no more than two zeros. Your task is to determine how many such numbers exist.

Input

You will receive an integer n from the standard input. The constraints are: 1 ≤ n ≤ 50.

Output

Print the number of binary numbers that meet the specified conditions to the standard output.

Examples