题目描述
军军有一个由若干个六边形构成的三⻆网格,如下图所示
每个六边形格子里面有一个独一无二的标记,现在军军将某些格子的标记锁定,锁定的格子的标记不能与相邻的格子标记进行交换
现在给你一个二维字符数组S 用来描述整个网格
s[i][j] 表示第i 行的第j 个字符
如果S[i][j] =′ X′,表示这个格子被锁定了
如果S[i][j] =′ :′, 表示这个格子是自由的
军军可以执行如下操作任意次数,选择三个自由的格子,A,B,C, 这三个格子必须要有一个公共的顶点,将A 里面的标记移动到B 里面,将B 里面的标记移动到C 里面,将C 里面的标记移动到A 里面
军军想知道一共能产生多少不同的局面,对1e9 + 7 取模
两个局面不同当且仅当某一个标记在两个局面中处于不同的位置
输入
第一行输入一个整数n 表示行数
接下来n 行每行输入一个字符串,第i 行包含i 个字符(1 <= i <= n)
1 <= n <= 50
输出
输出一个整数
样例输入
【样例输入1】
4
.
.X
X..
.X.X
【输入样例2】
1
X
【输入样例3】
4
.
..
...
.X..
样例输出
【输出样例1】
3
【输出样例2】
1
【输出样例3】
20160
提示
来源/分类