미로 틱택토

소 베시는 미로 푸는 것을 좋아한다. 그리고 소 버전 틱택토(잠시 후 설명한다) 놀이도 좋아한다. 농부 존은 베시가 두 놀이를 동시에 즐길 수 있는 새로운 방법을 찾아냈다!

먼저 소 틱택토부터 알아보자. $3 \times 3$ 격자에 X와 O를 놓는 대신, 소들은 당연히 $3 \times 3$ 격자에 M과 O를 가지고 논다. 자기 차례에 빈 칸 아무 곳에 'M' 또는 'O'를 놓을 수 있다(표준 틱택토에서는 한 플레이어가 항상 'X'를, 다른 플레이어가 항상 'O'를 놓는다는 점과 또 다른 차이다). 소 틱택토의 승자는 가로, 세로, 대각선 중 한 방향으로 'MOO'를 먼저 만든 플레이어다. 거꾸로 읽어도 되므로, 예를 들어 한 줄에 'OOM'을 만들어도 이길 수 있다. 표준 틱택토와 마찬가지로 아무도 이기지 못한 채 끝나는 판 상태에 도달할 수도 있다. 소 틱택토의 한 수는 보통 3글자로 표기하며, 'Mij' 또는 'Oij' 형태다. 여기서 $i$와 $j$는 각각 $1 \ldots 3$ 범위의 정수로, 해당 'M' 또는 'O'를 놓을 행과 열을 나타낸다.

베시에게 도전하기 위해 농부 존은 $N \times N$ 칸 격자로 이루어진 정사각형 미로를 설계했다($3 \leq N \leq 25$). 모든 테두리 칸을 포함한 일부 칸에는 커다란 건초더미가 있어 베시가 그 칸으로 이동할 수 없다. 베시는 미로의 나머지 칸 사이를 북, 남, 동, 서 네 방향으로 자유롭게 이동할 수 있다. 일부 칸에는 소 틱택토의 한 수가 적힌 종이가 있다. 베시가 미로를 돌아다니면서 그런 칸을 밟을 때마다, 미로를 이동하는 동안 동시에 진행 중인 소 틱택토 게임에서 해당 수를 두어야 한다(단, 소 틱택토 게임의 해당 칸이 이미 차 있으면 아무 행동도 하지 않는다). 이 소 틱택토 게임에는 상대가 없지만, 언젠가 'MOO'를 만드는 베시의 목표에 적대적인 칸도 미로에 있을 수 있다.

베시가 이기자마자 소 틱택토를 멈춘다면, 미로를 적절히 이동하여 만들어 낼 수 있는 서로 다른 승리 틱택토 판 구성의 수를 구하시오.

첫째 줄에 $N$이 주어진다.

미로는 다음 $N$개의 줄로 주어지며, 각 줄은 $3N$개의 문자를 포함한다. 각 칸은 3문자 블록으로 표현되는데, '###'는 벽, '...'는 빈 공간, 'BBB'는 베시가 있는 비벽 칸, 그리고 그 외의 비벽 칸은 베시가 해당 수를 두도록 강제하는 소 틱택토 수다. 'BBB'인 칸은 정확히 하나다.

베시가 미로를 이동하면서 만들어 낼 수 있는 서로 다른 승리 소 틱택토 판 구성의 수(0일 수도 있다)를 출력하시오. 이기는 즉시 멈춘다.

이 예에서 베시가 최종적으로 도달할 수 있는 승리 판 구성은 8가지다:

O.M
.O.
MOM

O..
.O.
.OM

O.M
.O.
.OM

O..
.O.
MOM

O..
...
OOM

..M
.O.
OOM

...
.O.
OOM

...
...
OOM

그중 하나를 설명하자면, 다음 경우를 보자:

O..
...
OOM

베시는 먼저 O11 칸을 방문한 뒤 아래쪽 통로로 이동하여 O32, M33, O31을 차례로 방문할 수 있다. 이기고 나면 게임이 즉시 끝난다(따라서 O31 칸에서 북쪽에 있는 M11 칸에는 방문할 수 없다).