Description

Consider a regular grid with $3 \times N$ points. Each point in the grid has at most eight adjacent points (see Figure $1$).

We are interested in counting the number of different ways to connect the grid points to form a polygon that satisfies the following conditions:

1. The set of vertices of the polygon consists of all $3 \times N$ points.
2. Adjacent vertices of the polygon are adjacent points in the grid.
3. Each polygon must be simple, i.e., it must not have any self-intersections.

Two possible polygons when $N = 6$ are shown in Figure $2$.

Write a program that, for a given $N$, computes the number of possible ways to connect the points. Output the answer modulo $10^9$.

Input Format

The only line contains a positive integer $N$.

Output Format

The only line contains one integer: the number of ways to connect these points modulo $10^9$.

3

8

4

40

Hint

Constraints

For $30\%$ of the testdata, $0 < N \le 200$.
For $70\%$ of the testdata, $0 < N \le 10^5$.
For $100\%$ of the testdata, $0 < N \le 10^9$.

Notes

This problem comes from Baltic Olympiad in Informatics 2007, Day 2:points.
Translated and整理 (zhěng lǐ, organized) by @求学的企鹅.

Input Format

Output Format

Hint

Translated by ChatGPT 5