Y was looking for a single sign of hope and then he saw a grid with two rows and $n$ columns. as a typical prison punishment Y is going to paint the grid.

Y thinks two cells are connected if they share a side and both are painted in the same color.

He also thinks there is a path between two cells $A$ and $B$ if there is a sequence of cells which starts with $A$ and ends with $B$ and any two consecutive cells in the sequence are connected.

Y calls a subset of grid's cells a connected component, if there is a path between any pair of subset's cells.

And at last, Y calls a connected component $C$ a maximal connected component, if there isn't any other connected component that includes $C$.

If Y paints a cell in black or white with the same probability (both $\frac{1}{2}$ ), what is the expected number of maximal connected components modular $10^9+7$ in the colored grid?

If the expected value is $\frac{P}{Q}$, print $P \times Q^{-1} \mod 10^9+7$.

Input

First and the only input line contains only $n$, number of grid's columns.

$1 \leq n \leq 10^{18}$

Output

The only line of output contains an integer, expected number of maximal connected components modular $10^9+7$.