Hamiltonian Polygon on a 3×N Grid

Consider a regular grid of points with 3 × N points. Each point in the grid has up to eight neighbours (i.e. two points are neighbours if their coordinates differ by at most 1 in each direction, excluding the same point). We are interested in counting the number of distinct ways to connect all grid points to form a polygon that satisfies the following conditions:

1. The set of vertices of the polygon is exactly the set of all 3 × N points.
2. Any two consecutive vertices in the polygon are adjacent in the grid (i.e. if the coordinates of two consecutive vertices are \((r_1,c_1)\) and \((r_2,c_2)\), then \(|r_1-r_2| \le 1\) and \(|c_1-c_2| \le 1\)).
3. The polygon is simple, i.e. its boundary does not cross itself.

Note that a polygon (or cycle) is considered independent of the starting vertex and the orientation. In other words, if a cycle is traversed in reverse order it is regarded as the same polygon.

It is known that if N is odd then the total number of grid points \(3N\) is odd and no such cycle exists. For even N one may form such Hamiltonian cycles. For example, when \(N=6\) two possible polygons are shown in Figure 2.

Your task is to compute the number of ways to form such a polygon (i.e. a Hamiltonian cycle on the induced grid graph with 8-directional adjacency) modulo \(10^9\).

Constraints: You may assume that N is small (for example, N up to 6). When N is odd, output 0.

Hint: One possible approach is to fix one vertex as the starting point and use a bitmask dynamic programming (DP) algorithm to count the number of Hamiltonian cycles. Since every valid cycle is counted twice (once in each direction), you must divide the final count by \(2\).

Formula note: The final answer is given by

[ answer = \frac{\displaystyle \sum_{\text{Hamiltonian paths ending at } v \text{ with } (v,0)\in E} dp[\text{full_mask}][v]}{2} \pmod{10^9}. ]

inputFormat

The input consists of a single integer N (N ≥ 1) on a line.

outputFormat

Output a single integer — the number of different Hamiltonian polygons (cycles) on the grid modulo 10^9.

Note: If N is odd then output 0.

sample

1

0