Tiling a 3 by N Wall

Count the tilings of a 3 by N wall with dominoes, modulo 1e9+7, where N can be as large as 10^18.

Medium7Dynamic programmingMatrixCombinatoricsNo attempts yetTime limit2sMemory limit512 MB

Description

Examples3

Problem

Count the ways to fill a $3 \times N$ wall completely with $2 \times 1$ tiles and $1 \times 2$ tiles. Tiles must not overlap and must not stick out of the wall. You may use any number of tiles of either shape.

Input

The first line contains $N$ ( $1 \le N \le 10^{18}$ ).

Output

Print the number of ways modulo $10^9 + 7$ on the first line.