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 12 ), what is the expected number of maximal connected components modular 109+7 in the colored grid?
If the expected value is PQ, print P×Q−1mod109+7.
Input
First and the only input line contains only n, number of grid's columns.
1≤n≤1018
Output
The only line of output contains an integer, expected number of maximal connected components modular 109+7.
As shown the expectation number of maximal connected components are:
1+2+2+2+2+2+4+2+2+4+2+2+2+2+2+14=344.