Hex 游戏是在一个由 $n \times n$ 个六边形组成的菱形六边形网格上进行的。下图展示了一个 $n = 5$ 的网格示例：
两名玩家分别持有自己的颜色，即红色和蓝色。玩家轮流进行，每回合一名玩家将一个尚未着色的六边形涂上自己的颜色。红方先手，当所有六边形都被涂色时游戏结束。
如果棋盘的左侧和右侧通过一条仅由红色六边形组成的路径相连，则红方获胜。如果棋盘的顶侧和底侧通过一条仅由蓝色六边形组成的路径相连，则蓝方获胜。该游戏的精妙之处在于这些条件是互斥的，而且不存在平局：最终总会有一名玩家获胜。
路径是指一系列六边形，其中每个六边形都与前一个六边形相邻（共享六条边中的一条）。四个角上的每个六边形都被视为与棋盘的两条边相连，换句话说，它可以作为任一颜色获胜路径的起点或终点。
给定 Hex 游戏进行过程中的当前状态。考虑该游戏可能达到的所有完全着色的棋盘状态。其中有多少种情况红方获胜？
输入格式
第一行包含一个整数 $n$，$2 \le n \le 12$。
接下来的 $n$ 行按行描述棋盘，如上图所示。每行包含 $n$ 个字符。每个字符为以下之一：
.（点）表示尚未着色的六边形R（大写字母 R）表示已涂成红色的六边形B（大写字母 B）表示已涂成蓝色的六边形
保证给定的棋盘是 Hex 游戏中的合法中间状态，即红色六边形的数量等于或比蓝色六边形的数量多一个。
输出格式
输出一个整数：红方获胜的最终棋盘数量。注意，我们只统计不同的最终棋盘，达到该状态的移动顺序无关紧要。
样例
输入 1
2 R. ..
输出 1
1
输入 2
12 ............ ............ ............ ............ ............ ............ ............ ............ ............ ............ ............ ............
输出 2
740106499224393094996908447741294397438050
说明
在第一个样例中，红方获胜的唯一最终棋盘如下所示：
在第二个样例中，由于一切都是对称的，红方在所有 $\binom{144}{72}$ 种可能的最终棋盘中正好有一半获胜，即 $\frac{1}{2} \cdot \binom{144}{72} = 740106499224393094996908447741294397438050$。
如果您使用 Java 提交此题，请使用特殊的编译器“Oracle Java 8 (48ML)”和“Oracle Java 7 x32 (48ML)”。这些编译器在执行您的解决方案时会向 Java 环境传递 -Xmx48M 标志，确保您有 48 MiB 的堆内存可用。这些编译器的实际内存限制设置得更高，以允许一定的 JVM 开销。对于所有其他语言，包括其他版本的 Java，内存限制均设置为 48 MiB。