# Problem E

Digbuild

Languages
en
is
Most of us like playing video games. Benni prefers to play
the video game *Digbuild*. *Digbuild* is
primarily about surviving for as long as possible. In the game
almost everything is possible. You can climb mountains, build
castles, and fish, just to name a few options. The gameworld
consists of large cubes, all the same size, whose corners are
always in integral coordinates in three dimensional space. The
player can both break these cubes (or blocks) and place blocks
next to ones already there. There are also other items in the
gameworld, auxiliary to these blocks. A few examples would be
beds to sleep on, frames for photographs, and torches to light
the world.

Benni isn’t a fan of building. He’d much rather dig tunnels in the ground. Benni always digs his tunnels horizontally and parallel to the $x$-axis of the gameworld. They are also always $3$ blocks high and $3$ blocks wide. Benni has just finished digging an $n$ block long tunnel and decided to go get a glass of water. When he sits down again to play some more he notices the tunnels are rather poorly lit. He realizes he has to place some torches on the floor of his tunnel to light the up. Benni is rather insistent on his tunnel not becoming ugly so he has to places the torches strategically. Benni considers his tunnel to be ugly if two blocks sharing a face both hold a torch.

In *Digbuild* you can only place one torch per block.
Benni is so against his tunnel being ugly he’d rather have them
unlit completely (i.e. not placing a torch is not considered
ugly).

In how many different ways can Benni place the torches such that his tunnel doesn’t become ugly? Since this number may be rather large you are asked to find the answer $\mod 10^9 + 7$.

## Input

The first and only line in the input contains the integer $1 \leq n \leq 10^{18}$.

## Output

The only line in the output should contain the number of non-ugly torch arrangements in an $n$ block long tunnel, $\mod 10^9 + 7$.

Sample Input 1 | Sample Output 1 |
---|---|

1 |
5 |

Sample Input 2 | Sample Output 2 |
---|---|

4 |
227 |

Sample Input 3 | Sample Output 3 |
---|---|

100 |
457171387 |