e-olymp

Zoo

prb157new

The n zoo cages are arranged in a row. In the zoo, besides other inhabitants, two monkeys live, Glory and Jura. Glory and Jura have always been great friends and sat in the neighboring cells, but now they quarreled and did not want to see each other. Superintendent was about to resettle them in accordance with their wishes, but there is a problem. Glory and Jura are very educated monkeys (they graduated from the eighth classes as much!), And they certainly want to know how many ways is there to settle them so that their cells were not neighbors, and certainly their cells must be different. Assume that all n cells are available, the remaining inhabitants of the zoo are ready to move anywhere.

The superintendent tried to count them himself, but he lost the count somewhere in the region of hippos. And clearly, without your help he can not cope!

Input

The number of cages n (2n100) in the zoo.

Output

Print the number of ways to settle the Glory and the Jura in different cells so that these cells will be not adjacent.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
Output example #1
2
Input example #2
4
Output example #2
6