Baltic OI '07 P5 - Connected Points

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem types
Baltic Olympiad in Informatics: 2007 Day 2, Problem 2

Consider a regular grid of 3N points. Every point in the grid has up to eight neighboring points (see Fig. 1). We are interested in counting the number of different ways to connect the points of the grid to form a polygon that fulfills the following conditions:

  1. The set of vertices of the polygon consists of all 3N 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 Figure 2.

Write a program that calculates for a given N the number of possible ways to connect the points as described modulo 10^9.


Figure 1: Neighboring points (marked by arrows).

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

Constraints

1 \le N \le 10^9

Subtask 1 [40%]

1 \le N \le 200

Subtask 2 [40%]

1 \le N \le 10^5

Subtask 3 [20%]

No additional constraints.

Input Specification

The first and only line contains one positive integer N.

Output Specification

Output the number of ways to connect the points modulo 10^9.

Sample Input 1

3

Sample Output 1

8

Sample Input 2

4

Sample Output 2

40

Comments

There are no comments at the moment.