Five-Dimensional Chocolate

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.

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

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