题目描述

有一个正八面体，它的每个三角形表面都被分割成 $n^2$ 个全等的小三角形：在每条边的方向上画 $n-1$ 条平行线，共画 $3(n-1)$ 条线。部分小三角形为黑色，其余为白色。

现在要使用“三角多米诺骨牌”覆盖所有白色小三角形，且不能覆盖任何黑色小三角形。一块三角多米诺由两个有公共边的小三角形组成。多米诺可以跨越八面体相邻两个面的公共边，也就是说它可以沿八面体棱“折弯”。

每个白色小三角形必须被恰好一块多米诺覆盖。求合法覆盖方案数。

输入格式

第一行一个整数 $n$，$1\le n\le4$。

接下来 $2n$ 行按水平层描述整个八面体。设八面体竖直放置，最上方和最下方各有一个顶点：

• 最顶层有 $4$ 个小三角形；
• 下一层有 $12$ 个；
• 此后每下一层增加 $8$ 个，直到中间层达到 $8n-4$ 个；
• 中间连续两层都含 $8n-4$ 个小三角形，之后层大小对称递减，直到最底层重新变为 $4$ 个。

每一层从图中可见部分最左侧的小三角形开始，从左到右描述可见的四个面，然后转到不可见部分并从右向左继续描述。字符 . 表示白色小三角形，* 表示黑色小三角形。

因此第 $i$ 行（从 $0$ 开始计层）的长度依次为 $4,12,20,\ldots,8n-4,8n-4,\ldots,20,12,4$。

输出格式

输出一个整数，表示用三角多米诺恰好覆盖所有白色小三角形的方案数。

样例 1

2
.***
........*...
************
....

2

样例 2

3
....
************
....................
********************
............
****

8