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\).