Baltic Olympiad in Informatics: 2007 Day 2, Problem 2
Consider a regular grid of 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:
The set of vertices of the polygon consists of all points.
Adjacent vertices of the polygon are neighboring points in the grid.
Each polygon is simple, i.e. there must not be any self-intersections.
Two possible polygons for are given in Figure 2.
Write a program that calculates for a given the number of possible ways to connect the points as described modulo .
Figure 1: Neighboring points (marked by arrows).
Figure 2: Two possible connections of points for .
Constraints
Subtask 1 [40%]
Subtask 2 [40%]
Subtask 3 [20%]
No additional constraints.
Input Specification
The first and only line contains one positive integer .
Output Specification
Output the number of ways to connect the points modulo .
Sample Input 1
3
Sample Output 1
8
Sample Input 2
4
Sample Output 2
40
Comments