There is an ant standing at vertex \(D\) of some tetrahedron. Let's label the other three vertices \(A\), \(B\) and \(C\), like so:

The ant doesn't like to stand still. At each moment in time the ant moves from one vertex to another, along some edge of the tetrahedron. The ant cannot stand on one place (vertex).

Your task is to count the number of ways in which the ant can go from the initial vertex (\(D\)) to itself in exactly \(n\) steps. In other words, you are asked to find out the number of different cyclic paths with the length of \(n\) from vertex \(D\) to itself. The number of paths can be quite large, print it modulo \(10^9 + 7\).

Sample input

On one line a single integer will be given: \(n\) (\(1 \leq n \leq 10^7\))

Sample output

Output the number of cyclical paths starting from vertex D to itself, modulo \(10^9 + 7\).

Example input

2

Example output

3

Example input

4

Example output

21

Example analysis

For the example, we have the following three paths:

• \(D \rightarrow A \rightarrow D\)
• \(D \rightarrow B \rightarrow D\)
• \(D \rightarrow C \rightarrow D\)

For the second example, two of the 21 paths are \(D \rightarrow A \rightarrow B \rightarrow C \rightarrow D\) and \(D \rightarrow A \rightarrow D \rightarrow A \rightarrow D\).