연결된 점 timer 1s memory 256MB

3×N의 격자형의 각각의 위치에 점이 찍힌 평면을 생각해보자. 그리고 아래와 같이 각 점은 8개의 이웃을 가진다.

위의 평면에서 다음의 조건을 만족하는 다각형을 몇 개를 만들 수 있는지에 대해 알아보고자 한다. 조건은 아래와 같다.

1. 다각형은 3×N의 다각형을 모두 포함해야 한다. 2. 이웃점끼리 직선으로 이을 수 있다. 3. 만들어지는 다각형은 반드시 단순 다각형이어야 한다. 즉, 다각형을 이루는 선끼리 겹치는 점이 없어야 한다.

만들어지게 되는 다각형의 예시는 다음과 같다.

N이 주어졌을 때 3 X N의 격자 점 평면에서 위의 조건을 만족시키면서 만들 수 있는 다각형의 숫자를 출력하는 프로그램을 작성하라.