Connecting Points

Time limit1sMemory limit128 MB

Summary
Count simple Hamiltonian polygons using all 3xN grid points with king-move adjacency, for N up to 1e9, mod 1e9.
Level

Hard8 of 10

Topics
Combinatorics, Dynamic programming, Math
Solved
No attempts yet

Problem

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.

Input

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

Output

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

Examples2

  1. Example 1

    Input
    3
    Expected output
    8

  2. Example 2

    Input
    4
    Expected output
    40