Maze Tac Toe timer 1초 memory 512MB

Bessie the cow enjoys solving mazes. She also enjoys playing tic-tac-toe (or rather, the cow version of tic-tac-toe, described shortly). Farmer John has found a new way for her to play both games at the same time!

First, cow tic-tac-toe: instead of placing X's and O's on a 3×3 grid, the cows of course play with M's and O's on a 3×3grid. During one's turn, one can place either an 'M' or an 'O' on any empty grid cell (this is another difference from standard tic-tac-toe, where one player always plays 'X' and other other always plays 'O'). The winner of cow tic-tac-toe is the first player to spell 'MOO', either horizontally, vertically, or diagonally. Backwards is fine, so for example a player could win by spelling 'OOM' across one row of the board. Just as in standard tic-tac-toe, it is possible to reach a board state where no winners occur. A move in cow tic-tac-toe is usually specified by 3 characters, either 'Mij' or 'Oij', where i and j are each in the range 1…3 and specify the row and column in which to place the corresponding 'M' or 'O'.

To challenge Bessie, Farmer John has designed a square maze consisting of a grid of N×N cells (3≤N≤25). Some cells, including all of the border cells, contain large haybales, preventing Bessie from moving onto any such cell. Bessie can move freely among all the other cells in the maze, by taking steps in the 4 usual directions north, south, east, and west. Some cells contain a piece of paper on which a move in cow tic-tac-toe is written. While Bessie moves around in the maze, any time she steps on such a cell, she must make the corresponding move in a game of cow tic-tac-toe that she is simultaneously playing while she moves through the maze (unless the corresponding cell in the cow tic-tac-toe game is already occupied, in which case she takes no action). She has no opponent in this game of cow tic-tac-toe, but some of the cells in the maze may be adversarial to her goal of eventually spelling 'MOO'.

If Bessie stops playing cow tic-tac-toe immediately upon winning, please determine the number of distinct winning tic-tac-toe board configurations she can possibly generate by moving appropriately through the maze.