#893 DT-Tiling

Statement

Statement language

Tile a $2\times N$ rectangular grid completely using dominoes and trominoes.

A domino consists of two unit squares joined along an edge. Both of the following types of trominoes are available.

A straight tromino consisting of three unit squares in a row.
An L-shaped tromino obtained by removing one cell from a $2\times2$ square.

Tiles may be rotated to align with the grid, and an unlimited number of each type is available. Tiles must not overlap or extend outside the grid.

Find the number of tilings modulo $1\,000\,000\,007$ . Two tilings are different if their collections of cell sets occupied by individual tiles are different. Tiles of the same shape are indistinguishable.

Input

The input is given in the following format:

$N$

Output

Print the number of tilings modulo $1\,000\,000\,007$ .

Constraints

$1\leq N\leq10^{18}$ .
$N$ is an integer.

Subtasks

#	Score	Constraints
1	20	$N\leq20$ .
2	50	$N\leq10^6$ .
3	30	No additional constraints.

Samples

Sample 1

Input

3

Output

6

There are $3$ tilings using only dominoes, $2$ using two L-shaped trominoes, and $1$ using two straight trominoes.

Sample 2

Input

4

Output

17