0 人解决，6 人已尝试。
0 份提交通过，共有 15 份提交。
9.9 EMB 奖励。
2376. Connected Points
单点时限: 2.0 sec
内存限制: 256 MB
Consider a regular grid of 3 × N points. Every point in the grid has up to eight eighboring 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 3 × N 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 N = 6 are given in the Fig. 2.
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.
输入格式
The first and only line contains one positive integer N (N ≤1,000,000,000).
输出格式
The only line to be written contains the remainder of the number of ways to connect the points modulo 1,000,000,000.
样例
Input
3 /* 4 */
Output
8 /* 40 */
题目标签