CONNECTE - Connected Points

no tags 

Consider a regular grid of 3 × N points. Every point in the grid has up to eight neighboring points (see figure 1).

Figure 1: Neighboring points (marked by arrows).

We are interested in counting the number of different ways to connect the points of the grid to form a polygon that fulfils the following conditions: 1. The set of vertices of the polygon consists of all 3 × N points. 2. Adjacent vertices of the polygon are neighboring points in the grid. 3. Each polygon is simple, i.e. there must not be any self-intersections. Two possible polygons for N = 6 are given in the figure 2.

Figure 2: Two possible connections of points for N = 6.

Write a program that calculates for a given N the number of possible ways to connect the points as described modulo 1,000,000,000.

Input

The first and only line contains one positive integer N (N <= 1,000,000,000).

Output

The only line to be written contains the remainder of the number of ways to connect the points modulo 1,000,000,000.

Example

Input:
3

Output:
8
Input:
4

Output:
40



Added by:sieunhan
Date:2009-05-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Resource:BOI