Problem 270
Cutting Squares
A square piece of paper with integer dimensions N×N is placed with a corner at the origin and two of its sides along the x- and y-axes. Then, we cut it up respecting the following rules:
- We only make straight cuts between two points lying on different sides of the square, and having integer coordinates.
- Two cuts cannot cross, but several cuts can meet at the same border point.
- Proceed until no more legal cuts can be made.
Counting any reflections or rotations as distinct, we call C(N) the number of ways to cut an N×N square. For example, C(1) = 2 and C(2) = 30 (shown below).
What is C(30) mod 108 ?
切割正方形
将一张边长为整数、大小为N×N的正方形纸的顶点置于原点，两条相邻边分别贴着x轴和y轴。然后，我们根据下面的规则对它进行切割：
- 我们只进行这样的切割：从正方形不同的两条边上选择两个坐标为整数的点，并沿着两点的连线切割。
- 两次切割不能相交，但多次切割可以经过边上的同一个点。
- 一直切割下去，直到不存在合法的切割为止。
如果翻转或旋转后相同的切割方法视为不同，我们记切割一个N×N方块的方法数记为C(N)。举例而言，C(1) = 2，而C(2) = 30（如下图所示）。
C(30) mod 108是多少？