Connecting Points

There is a rectangular grid containing 3 x N points. Each point in the grid can be connected to up to 8 neighboring points around it.

Count how many polygons can be made by connecting points on the grid. A polygon must satisfy all of the following conditions.

1. All 3 x N points must be used as vertices.
2. Two adjacent vertices in the polygon must also be neighboring points in the grid.
3. The polygon must be simple. In other words, its edges must not cross.

The picture below shows two possible polygons when N = 6.

Given N, write a program that computes the number of polygons that can be made.

The first line contains a positive integer N. (N <= 1,000,000,000)

Print the number of polygons that can be made, modulo 1,000,000,000.