정수 치수 N×N인 정사각형을 한 꼭지점을 원점에 그리고 두 변을 x축, y축을 따라 놓습니다. 그런 다음, 아래 규칙에 따라 자릅니다:

• 서로 다른 변에 있는 두 정수 좌표 점을 연결한 직선으로 자릅니다.
• 두 절단선은 교차할 수 없습니다. 그러나 가장자리의 한 점에서 여러 절단선이 만날 수는 있습니다.
• 더이상 규칙에 맞게 자를 수 없을 때까지 계속합니다.

반사나 회전 된 것을 다르다고 보고, C(N)을 N×N 정사각형을 자르는 방법의 수라고 합니다. 예를 들어, C(1) = 2이고 C(2) = 30(아래 그림)입니다.

C(30) mod 10⁸값은 얼마입니까?