Expectation

3.5

8 votes
Algorithms, Bit Manipulation, Dynamic Programming, Matrix
Problem

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×Q1mod109+7.

Input

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

1n1018

Output

The only line of output contains an integer, expected number of maximal connected components modular 109+7.

Sample Input
2
Sample Output
125000003
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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.

Editor Image

?