计算满足拼接规则的拼图拼法总数

题目描述

小利准备将 n 块拼图从左到右进行拼接，每块拼图原本为大小一致的正方形卡片，每条边都做了改变，共有 8 种不同的边，使用编号 1 - 8 表示。每块拼图使用其 上、右、下、左 四条边的编号来表示。

例如，下面两块拼图共有 8 种不同的边，左边的拼图用 1234 表示，右边的拼图用 5678 表示：

拼图规则

1. 拼接配对规则：

• 1 号边只能与 8 号边拼接
• 2 号边只能与 7 号边拼接
• 3 号边只能与 6 号边拼接
• 4 号边只能与 5 号边拼接

2. 你可以将每块拼图顺时针旋转 0 度、90 度、180 度、270 度来进行拼图（不能翻转到另一面进行拼图）。例如，同一块拼图旋转不同度数时的效果如下图所示：

• 旋转 0 度：上边为 1，右边为 2，下边为 3，左边为 4
• 旋转 90 度：上边为 4，右边为 1，下边为 2，左边为 3
• 旋转 180 度：上边为 3，右边为 4，下边为 1，左边为 2
• 旋转 270 度：上边为 2，右边为 3，下边为 4，左边为 1

3. 除第一块拼图外，下一块拼图只能拼在已拼接拼图的最右边。

注

在各种拼法中，只要有任意一个相同位置上的拼图不一致，或拼图相同但旋转的方向不一致，都算不同的拼法。 本题中，n 块拼图是不同的，不存在以下两种情况：

1. 同一块拼图，旋转 90 度、180 度、270 度后，不会出现与 0 度相同的情况。
2. 任意两块拼图，不会出现其中一块拼图旋转后与另一块相同。

例如：n = 3；3 块拼图分别是 4524、6134、3872，如下图所示： 一共有 4 种不同的拼法，如下图所示：

输入描述

1. 第一行输入一个整数 n（2 ≤ n ≤ 8），表示拼图的块数；
2. 第二行输入 n 个长度为 4 的字符串，字符串仅包含数字 1 - 8，字符串之间以一个空格隔开，每个字符串从左至右的 4 个数字依次表示该块拼图 上、右、下、左 四条边的编号。

输出描述

输出一个整数，表示多少种不同的拼法。

输入样例

3
4524 6134 3872

输出样例

4

提示

本题 10 组测试用例，每通过一题得 8 分。