As long as the students have final exams, the teachers play mafia game. In the circle sits n teachers. The dealer should give to some of them one card with Ace (any amount of Aces is possible, even can be 0) - these teachers are the mafia. However, no two mafiosi can sit next to each other.

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

Input

Number of teachers n (1 ≤ n ≤ 30) siting in a circle.

Output

Print the number of ways to deal the cards.