题目描述

在一所神秘的魔法学院里，聪明好学的学生 「哈利波特」正在探索学院中隐藏的魔法谜题。有一天，他来到了一个充满魔法阵的神秘房间，房间里有一个由 $N\times N$ 个方格组成的巨大魔法阵迷宫（$3\le N\le 25$）。其中一些方格被强大的魔法封印保护着，里面有神秘的魔法力量， 「哈利波特」一旦触碰就会被魔法力量束缚，无法进入这些方格。但是， 「哈利波特」可以在其他未被封印的方格中自由移动，他可以沿着东南西北四个方向穿梭于魔法阵之间。

在这个魔法阵迷宫中，存在着一些特殊的魔法符文方格。当 「哈利波特」进入到这些方格时，他会触发一个奇妙的魔法谜题——魔法井字棋。这个游戏的棋盘是一个 $3\times 3$ 的魔法方格，用于记录魔法井字棋的棋盘局面。

与普通的井字棋不同，在这个魔法井字棋游戏中， 「哈利波特」每次进入一个魔法符文方格时，都可以在 $3\times 3$ 的棋盘上放置一个代表不同魔法力量的符号 M 或者 O 。他需要根据魔法符文的要求进行放置 M 或者 O（魔法符文用3个字符表示，Mij 或 Oij，其中 $i$ 和 $j$ 在范围 $1\dots 3$ 之间，表示放置 M 或 O 的行与列）。

这个魔法井字棋的胜利条件是：首位拼出 MOO 或者 OOM 的玩家获胜，也就是在棋盘的同行、同列或者对角线上形成这样的魔法组合就算胜利。

然而，有些特殊的是，当 「哈利波特」进入这些魔法符文方格时，如果对应的魔法井字棋棋盘方格已经被填上了符号，那么他这次就不能再进行放置操作了。

现在， 「哈利波特」想要知道，通过他在魔法阵迷宫中巧妙地移动，能够完成多少种不同的最终获胜状态下的魔法井字棋棋盘呢？也就是说，当 「哈利波特」在魔法阵迷宫中移动并触发魔法井字棋游戏，最终达成胜利条件时，那些不同的获胜棋盘布局有多少种可能性呢？

输入格式

从文件 $magic.in$ 中读入数据。

输入的第一行包含 $N$。

以下 $N$ 行，每行包含 $3N$ 个字符，描述迷宫。

每个方格用 $3$ 个字符表示，### 代表被魔法封印的方格，... 代表未被魔法封印的方格，BBB 代表 「哈利波特」 所在的一个未被魔法封印的方格，Mij 或 Oij 表示一个魔法符文，是 「哈利波特」 必须进行对应行动的一个方格。恰好一个方格为 BBB。

输出格式

输出答案到文件 $magic.out$ 中。

输出 「哈利波特」 可以通过在魔法阵迷宫中行动并在获胜时立刻停止而产生的不同的胜利状态下的魔法井字棋棋盘数量（可能为 $0$）。

输入输出样例 #1

输入 #1

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

输出 #1

8

说明/提示

样例说明

在这个样例中， 「哈利波特」 最终可能达成 $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 方格）。

数据范围

$3\le N\le 25$

大样例下载