P7657 [BalticOI 2007] Connected Points (Day 2)

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. 1. Adjacent vertices of the polygon are adjacent points in the grid. 1. 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$.

The only line contains a positive integer $N$.

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

#### 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](https://www.boi2007.de/en/welcome), [Day 2:points](https://www.boi2007.de/tasks/points.pdf). Translated and整理 (zhěng lǐ, organized) by @[求学的企鹅](/user/271784). # Input Format # Output Format # Hint Translated by ChatGPT 5