Hide

Problem D
Lines of X

Tic-tac-toe is boring. The optimal strategy is simple to work out. But what about a generalization to an $N \times N$ board. That also does not seem interesting, and you probably won’t convince anyone to play with you. So you decide to have your own fun with such grids.

Given a $N \times N$ grid $G$ where each cell contains a single X, O, or . (the latter meaning the space is empty), you want to calculate the number of ways one can fill out the empty cells in $G$ so that there is at least one line that is all X. The lines of the grid are the $N$ rows, the $N$ columns, and the $2$ diagonals.

More precisely, compute the number of $N \times N$ grids $H$ that have the following properties:

  • $H$ contains only X or O entries, no empty cells.

  • The only cells where $G$ and $H$ can differ is at the empty cells in $G$.

  • At least one row, column, or diagonal line of $H$ only contains X.

Input

The first line of input contains a single integer $N$ ($2 \leq N \leq 8$) indicating the dimensions of the grid. The next $N$ lines describe the rows of the grid, each row is a string of length exactly $N$ containing only characters ., O, X.

Output

Output a single number indicating the number of ways to fill out the . characters in the grid with either O or X so that the resulting grid has at least one line with all characters being X.

Sample Input 1 Sample Output 1
2
X.
..
7
Sample Input 2 Sample Output 2
2
X.
.O
3
Sample Input 3 Sample Output 3
3
XO.
O.X
OXO
0
Sample Input 4 Sample Output 4
2
XX
XX
1

Please log in to submit a solution to this problem

Log in