Koza Nostra

While the students are taking their exams, the teachers play Mafia. There are $n$ teachers sitting in a circle. The dealer must distribute cards with aces (any number of aces, possibly $0$) to some of them, and those teachers will be the Mafia. However, no two Mafia members should sit next to each other.

In how many ways the dealer can distribute the cards? Two ways are considered different if there is at least one teacher who is Mafia in one case, but not Mafia in the other.

Input

Number of teachers $n(1\le n\le 30)$ siting in a circle.

Output

Print the number of ways to deal the cards.

Examples