Maze Tac Toe
奶牛 Bessie 喜欢玩走迷宫。她同样喜欢玩井字棋（更准确地说，奶牛版的井字棋，马上会进行介绍）。Farmer John 找到了一种全新的方式，可以使她同时玩到这两种游戏！
首先，奶牛井字棋：与在 $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` 的行与列。
为了给 Bessie 增加一些挑战，Farmer John 设计了一个由 $N \times N$ 个方格组成的正方形迷宫（$3 \leq N \leq 25$）。某些方格，包括所有的边界方格，有巨大的草堆，使得 Bessie 不能移动到这些方格。Bessie 可以沿东南西北四个方向在迷宫内的所有其他方格内自由行动。某些方格内有一张纸，上面写有奶牛井字棋的一次行动。当 Bessie 在迷宫中移动时，任何时刻她停留在这样的方格上，她都必须于迷宫中移动之时在同时进行的奶牛井字棋游戏内做出对应的行动（除非奶牛井字棋中对应的方格已经被填上了，在这种情况下她不进行行动）。在奶牛井字棋游戏内没有与她对阵的玩家，但迷宫中的某些方格可能会不利于她最终拼出 `MOO`。
如果 Bessie 在获胜之时就会立刻停止奶牛井字棋，请求出她可以通过适当的方式在迷宫中移动而完成的不同的胜利状态棋盘数量。
输入格式
输入的第一行包含 $N$。
以下 $N$ 行，每行包含 $3N$ 个字符，描述迷宫。每个方格用 3 个字符表示，`###` 代表墙，`...` 代表空格，`BBB` 代表 Bessie 所在的一个非墙方格，或者一个奶牛井字棋的行动，表示 Bessie 必须进行对应行动的一个非墙方格。恰好一个方格为 `BBB`。
输出格式
输出 Bessie 可以通过在迷宫中行动并在获胜时立刻停止而产生的不同的胜利状态下的奶牛井字棋盘数量（可能为 $0$）。
样例 #1
样例输入 #1
7
#####################
###O11###...###M13###
###......O22......###
###...######M22######
###BBB###M31###M11###
###...O32...M33O31###
#####################
样例输出 #1
8
提示
样例说明
在这个样例中，Bessie 最终可能达成 $8$ 种胜利的棋盘状态：
```plain
O.M
.O.
MOM
O..
.O.
.OM
O.M
.O.
.OM
O..
.O.
MOM
O..
...
OOM
..M
.O.
OOM
...
.O.
OOM
...
...
OOM
```
对其中一种情况进行说明：
```plain
O..
...
OOM
```
在这里，Bessie 可以先移动到 `O11` 方格，然后移动到下方并通过 `O32`、`M33` 和 `O31`。此时游戏结束，因为她获得了胜利（例如她不能再前往位于她当前所在的 `O31` 方格北面的 `M11` 方格）。
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×3 grid. 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 pla
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.
The maze is specified by the next N lines, each containing 3N characters. Each cell described by a block of 3 characters, which is either '###' for a wall, '...' for an empty space, 'BBB' for a non-wall containing Bessie, and a cow tic-tac-toe move for a non-wall cell that forces Bessie to make the corresponding move. Exactly one cell will be 'BBB'.
7
#####################
###O11###...###M13###
###......O22......###
###...######M22######
###BBB###M31###M11###
###...O32...M33O31###
#####################8
In this example, there are 8 possible winning board configurations that Bessie can ultimately reach:
O.M .O. MOM O.. .O. .OM O.M .O. .OM O.. .O. MOM O.. ... OOM ..M .O. OOM ... .O. OOM ... ... OOM
To explain one of these, take this case:
O.. ... OOMHere, Bessie might first visit the O11 cell, then move to the lower corridor visiting O32, M33, and O31. The game then stops, since she has won (so for example she would not be able to visit the M11 cell north of her current position on the O31 cell).