Problem Statement

When $\left\lceil\frac{N}{2}\right\rceil$ people sit on a bench with $N$ seats so that no $2$ people are next to each other, how many possible states of occupied seats are there?

The following is a more rigorous statement. There is a bench with $N$ seats, numbered $1,2,\ldots,N$. For $i=1,2,\ldots,N-1$, seat number $i$ and seat number $i+1$ are adjacent. $\left\lceil\frac{N}{2}\right\rceil$ people each sit on one of the $N$ seats. No $2$ people may choose the same seat or adjacent seats. How many possible states of occupied seats are there? Here, $2$ states are considered different if there exists a number $i$ such that someone is sitting on seat $i$ in one state but no one is sitting on seat $i$ in the other.

Note that $\left\lceil\frac{N}{2}\right\rceil$ denotes the smallest integer greater than or equal to $\frac{N}{2}$.

Input

$N$

$N$ is an integer between $1$ and $10^9$, inclusive.

Output

Compute and print the number of possible states of occupied seats. Print a newline at the end.

Sample

2

2

5

1