Problem E
Digbuild

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 $\mathrm{mod}{10}^9+7$.

Input

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

Output

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

1

5

4

227

100

457171387