Pinary Numbers

A binary number is a number made only of 0s and 1s. A pinary number is a binary number that satisfies both of the following conditions.

1. It does not start with 0.
2. It never has two consecutive 1s. In other words, it does not contain the substring 11.

Numbers such as 1, 10, 100, 101, 1000, and 1001 are pinary numbers. On the other hand, 0010101 is not a pinary number because it starts with 0, and 101101 is not a pinary number because it contains 11.

Given an integer N, find the number of pinary numbers of length N. The value of N satisfies 1 <= N <= 90.

The first line contains the integer N.

Print the number of pinary numbers of length N on the first line.