Five-Dimensional Chocolate

Time limit2sMemory limit512 MB

Summary

Count the ways to tile a 2x2x2x2xn five-dimensional box with 1x1x1x1x2 domino pieces, modulo 1000000007.

Level: Hard8 of 10
Topics: Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

A chocolate bar of size $2 \times 2 \times 2 \times 2 \times n$ sits in a five-dimensional world. It consists of $16n$ unit cubes.

You want to cut it into $8n$ pieces of size $1 \times 1 \times 1 \times 1 \times 2$ . Write a program that counts the ways to cut it.

The orientation of a piece does not matter, so $1 \times 1 \times 1 \times 2 \times 1$ and $2 \times 1 \times 1 \times 1 \times 1$ are possible sizes too. Two ways are counted as different when some piece covers a different pair of unit cubes.

Input

The first line contains $n$ ( $1 \le n \le 10^9$ ).

Output

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

Examples3

Example 1
Input
```
1
```
Expected output
```
272
```
Example 2
Input
```
2
```
Expected output
```
589185
```
Example 3
Input
```
3
```
Expected output
```
930336768
```