CONNECTE - Connected Points
English | Vietnamese |
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 |