16222번 - Celtic Knots

그림 1. Celtic Knot의 예시 (N = 3)

그림 1은 Celtic Knot이라고 하는 아일랜드의 옛 그림에서 많이 볼 수 있는 매듭의 예시다 (출처). 예술가 JJ는 위 그림에 영감을 받아 자신의 그림에 들어갈 Celtic Knot을 그리고 있다. JJ는 매듭의 많은 부분을 완성했지만, 원래 그림에서 매듭이 교차하는 부분에 다양한 변화를 주고 싶다. 그래서 JJ는 일부러 그림 2와 같이 교차점들을 흰색 원들로 비워놨다.

그림 2. JJ가 비워놓은 Celtic Knot (N = 4)

JJ는 이제 그림에 있는 흰색 원들을 전부 그림 3의 4가지 형태 중 하나로 채우려고 한다. 각 흰색 원에는 4개의 실이 맞닿아 있으므로, 이 4개의 실을 4가지 중 어떤 방법으로 연결할 지 결정하는 것이다. 그림 3에서 나오는 방법들을 왼쪽부터 순서대로 1번, 2번, 3번, 4번 방법이라고 하자. 예를 들어, 그림 1의 매듭은 흰색 원들을 위에서부터 홀수 번째 줄들은 모두 1번 방법으로, 짝수 번째 줄들은 모두 2번 방법으로 채운 매듭이다.

그림 3. 흰색 원들을 채울 수 있는 방법들

JJ는 흰색 원들 중 몇군데를 이미 위 4가지 방법을 이용해 채워넣었다 (각 원에 채운 방법은 원마다 다를 수 있다). 이제 JJ는 나머지 원들을 채워서 하나의 연결된 매듭을 만들고 싶다. 즉, 매듭의 실 한 가닥을 쭉 따라가면 매듭의 모든 부분을 돌고 원래 자리로 돌아올 수 있게 하고 싶다는 것이다. 그림 1의 매듭은 3개의 연결된 부분이 엉킨 매듭이므로 조건을 만족하지 않는다. 하지만, 그림 1의 맨 아래줄의 교차점 두개를 3번 방법으로 채운다면 하나의 연결된 매듭이 나온다. JJ를 도와 미완성된 매듭의 나머지 부분을 채워 하나의 연결된 매듭을 만들 수 있는 방법의 총 가지수를 계산하자.

입력의 첫 줄에는 매듭의 크기 N이 주어진다. N은 2 이상 7 이하의 자연수다. JJ가 그릴 매듭은 빈 칸이 맨 윗줄부터 순서대로 N-1개, N개, N-1개, ..., N개, N-1개로 총 2N-1개 줄에 걸쳐 나타나있다.

다음 2N-1개 줄에는 현재 JJ가 그린 미완성된 매듭의 정보가 주어진다. 각 줄은 길이 2N-1의 문자열이다.

문자열은 문자 '.' 또는 '0', '1', '2', '3', '4'로 구성되어 있다. 문자 '.'는 입력을 이쁘게 하기 위한 문자로, 그 외의 의미는 없다. 문자 '0'은 JJ가 현재 비워놓은 흰색 원을 의미한다. 문자 '1'부터 '4'까지는 JJ가 해당하는 번호의 방법으로 이미 채워놓은 원을 의미한다. i번째 줄의 문자열에 나타나는 숫자들은 왼쪽부터 오른쪽 순서대로 매듭의 i번째 줄에 나타나는 원들의 상태를 의미한다.

홀수 번째 줄의 문자열은 항상 '.'으로 시작해 숫자와 '.'가 번갈아 나타난다. 마찬가지로, 짝수 번째 줄의 문자열은 항상 숫자로 시작해 '.'와 숫자가 번갈아 나타난다.

입력에서 '0'으로 나타낸 빈 공간들을 채워 하나의 연결된 매듭을 만들 수 있는 방법의 수를 출력한다. 가짓수가 많을 수 있으므로, 가짓수를 10¹⁸ 로 나눈 나머지를 출력한다.