Description

The cow Bessie likes playing maze-walking games. She also likes playing tic-tac-toe (more precisely, a cow version of tic-tac-toe, described below). Farmer John has found a brand-new way for her to play both games at the same time.

First, cow tic-tac-toe: instead of placing X and O on a $3 \times 3$ board, cows of course place M and O on a $3 \times 3$ board. On a player's turn, the player may choose to place either an M or an O in any empty cell (this is another difference from standard tic-tac-toe, where one player always places X and the other always places O). The winner of cow tic-tac-toe is the first player to spell MOO, which may appear in a row, a column, or a diagonal. Spelling it backwards also counts; for example, a player also wins by forming OOM in a row. Just like standard tic-tac-toe, it is possible that no player wins in the end. A move in cow tic-tac-toe is usually written using 3 characters, Mij or Oij, where $i$ and $j$ are in the range $1 \ldots 3$, indicating the row and column where the M or O is placed.

To make things more challenging for Bessie, Farmer John designed a square maze consisting of $N \times N$ cells ($3 \leq N \leq 25$). Some cells, including all boundary cells, contain huge haybales, so Bessie cannot move onto those cells. Bessie can move freely among all other cells in the maze in the four directions north, south, east, and west. Some cells contain a sheet of paper with a cow tic-tac-toe move written on it. As Bessie moves through the maze, whenever she is standing on such a cell, she must perform the corresponding move in the cow tic-tac-toe game that is being played at the same time as she moves through the maze (unless the corresponding cell in the cow tic-tac-toe board is already filled, in which case she does not make a move). There is no opponent player in the cow tic-tac-toe game, but some cells in the maze may be unfavorable for her to eventually form MOO.

If Bessie stops the cow tic-tac-toe game immediately upon winning, compute the number of distinct winning board states that she can achieve by moving through the maze in some suitable way.

Input Format

The first line contains $N$.

The next $N$ lines each contain $3N$ characters describing the maze. Each cell is represented by 3 characters: ### represents a wall, ... represents an empty cell, BBB represents the (non-wall) cell where Bessie starts, or a cow tic-tac-toe move, representing a (non-wall) cell where Bessie must perform the corresponding move. Exactly one cell is BBB.

Output Format

Output the number of distinct winning cow tic-tac-toe board states (possibly $0$) that Bessie can produce by moving through the maze and stopping immediately upon winning.

7
#####################
###O11###...###M13###
###......O22......###
###...######M22######
###BBB###M31###M11###
###...O32...M33O31###
#####################

8

Hint

Sample Explanation

In this sample, Bessie can end up achieving $8$ different winning board states:

O.M
.O.
MOM

O..
.O.
.OM

O.M
.O.
.OM

O..
.O.
MOM

O..
...
OOM

..M
.O.
OOM

...
.O.
OOM

...
...
OOM

One of these cases is explained below:

O..
...
OOM

Here, Bessie can first move to the O11 cell, then move downward and pass through O32, M33, and O31. At this point the game ends because she has won (for example, she can no longer go to the M11 cell north of her current O31 cell).

Note

Problem by: Brian Dean

Translated by ChatGPT 5