Bessie Maze Tic Tac Toe

Bessie loves wandering through mazes and playing a quirky version of tic-tac-toe. In cow tic-tac-toe the board is a $3 \times 3$ grid. Instead of the usual X and O markers, players may place either an M or an O in any empty cell. During a turn, a player may choose either letter (unlike standard tic-tac-toe where one player is fixed to one letter). A player wins if any row, column, or diagonal spells out either $MOO$ or $OOM$ (the winning word may appear in reverse order).

To challenge Bessie, Farmer John sets up a maze comprising an $N \times N$ grid ($3 \le N \le 25$). Certain cells – including all boundary cells – have tall hay bales (denoted by #) that block movement. Bessie may move in the four cardinal directions (north, south, east, west) through the remaining open cells. Some open cells contain a slip of paper with a cow tic-tac-toe move (a three‐character string such as Mij or Oij, where $i$ and $j$ are integers between 1 and 3 indicating the row and column of the tic‐tac-toe board). Whenever Bessie stops on such a cell, if the corresponding cell on the tic‐tac‐toe board is still empty, she must carry out that move. Note that the tic‐tac‐toe game is being played by Bessie alone; however, the moves provided by the maze may make it difficult for her to eventually win the game.

The twist is that as soon as the tic‐tac‐toe board reaches a winning configuration, Bessie stops playing further moves. Two winning board states are considered different if the final configuration of the $3 \times 3$ board differs.

Your task is to determine the number of distinct winning tic‐tac‐toe board states that Bessie can achieve by choosing an appropriate route through the maze. Bessie is allowed to start from any open cell (a cell that is not blocked by hay) and must obey the move instructions on the maze cells she visits – making a move if the indicated cell on the tic‐tac‐toe board is still empty. Once a winning board is attained, no subsequent moves are applied.

inputFormat

The input begins with an integer $N$ ($3 \le N \le 25$), the size of the maze. Following this are $N$ lines, each containing $N$ tokens separated by spaces. Each token is either:

• # indicating a blocked cell (hay bale), or
• . indicating an open cell with no move, or
• a three‐character string such as Mij or Oij indicating that this cell contains a tic‐tac‐toe move, where $i,j \in \{1,2,3\}$.

You may assume that all boundary cells are blocked (i.e. contain #).

outputFormat

Output a single integer representing the number of distinct winning tic‐tac‐toe board states Bessie can achieve by a valid movement in the maze.

sample

3
# # #
# O11 #
# # #

0