NC21707. 牛牛的六边形网格
描述
牛牛有一个由若干个六边形构成的三角网格，如下图所示
每个六边形格子里面有一个独一无二的标记，现在牛牛将某些格子的标记锁定，锁定的格子的标记不能与相邻的格子标记进行交换
现在给你一个二维字符数组S用来描述整个网格
s[i][j]表示第i行的第j个字符
如果S[i][j] = 'X'，表示这个格子被锁定了
如果S[i][j] = '.', 表示这个格子是自由的
牛牛可以执行如下操作任意次数，
选择三个自由的格子，A,B,C, 这三个格子必须要有一个公共的顶点，将A里面的标记移动到B里面，将B里面的标记移动到C里面，将C里面的标记移动到A里面
牛牛想知道一共能产生多少不同的局面，对1e9+7取模
每个六边形格子里面有一个独一无二的标记，现在牛牛将某些格子的标记锁定，锁定的格子的标记不能与相邻的格子标记进行交换
现在给你一个二维字符数组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
输出:
3
说明:
示例2
输入:
1 X
输出:
1
示例3
输入:
4 . .. ... .X..
输出:
20160