ladderGraph

A ladder graph L(N) is a planar graph with 2 * N nodes and N + 2 * (N - 1) edges. It is isomorphic to the grid graph with 2 lines and N columns:

You want to delete a subset (possibly empty) of its edges so that the graph stays connected. Count the number of valid subsets of edges you can delete and return it modulo 10⁹ + 7.

Source: Second round of 26^thinformatics olympiad in Iran.

Example

For N = "1", the output should be

LadderGraph(N) = 1.

There are two vertices in the graph, connected by a single edge. No edges can be removed, so only the empty subset should be counted.
For N = 2, the output should be

LadderGraph(N) = 5.

The graph looks as follows:

It is possible to remove an empty set of edges, or sets consisting of a single element – one of the edges. Thus, there are 5 sets altogether.

Input/Output

[execution time limit] 4 seconds
[input] string N

Half of the numbers of vertices.

Constraints:

1 ≤ N ≤ 2⁵¹.
[output] integer
- The answer modulo 10⁹ + 7