Magnetic Moves

With the auto-pilot running and the rocket cruising toward Earth, the crew finally has a chance to breathe. That first evening, they gather for iftar in zero gravity. Dr. Mkouli's farewell crate is unpacked: alien fruits, dates, milk, and plates of bourak floating gently through the cabin. Someone pulls out an old magnetic chessboard and challenges Adel to a match, but zero gravity has other plans. The queens keep drifting out of position, sliding across the board until the whole setup is a mess.

Before anyone can play, the board needs fixing. The queens must be rearranged so that no two of them threaten each other. On a chessboard, a queen threatens every cell in her row, column, and both diagonals.

Input Format

An N x N grid (one line per row) where o marks a queen and . marks an empty cell. There is exactly one queen per row. N queens total, N <= 16.

Each queen can slide any number of cells in one of the 4 cardinal directions (up, down, left, right) as a single move. Sliding from (2, 3) to (2, 0) counts as 1 move, not 3. Queens can pass over other queens (no blocking).

The cost to move one queen from its starting cell to its destination cell is:

• 0 if start and destination are the same cell (same row and same column).
• 1 if start and destination share the same row or the same column (but are not the same cell). One slide is enough.
• 2 if start and destination differ in both row and column. Two slides are needed: one horizontal and one vertical.

A target configuration is any placement of N queens on the N x N board such that no two queens share a row, column, or diagonal (a valid N-Queens arrangement).

Each of the N queens must travel from its starting cell to exactly one cell in the target configuration, and each target cell must receive exactly one queen. The total cost is the sum of the N individual movement costs.

Find the target configuration and the assignment of queens to target cells that together achieve the minimum total cost. Call this minimum total cost C.

Encoding

Let col_i be the column of the queen in row i of the target configuration (0-indexed rows and columns). Compute: result = col_0 * C^0 + col_1 * C^2 + col_2 * C^3 + col_3 * C^4 + ... + col_{n-1} * C^n

The exponent sequence is 0, 2, 3, 4, ..., n. Exponent 1 is skipped: the first term uses C^0, the second uses C^2, then C^3, C^4, and so on up to C^n.

If multiple target configurations (with their optimal assignments) achieve the same minimum cost C, choose the one that produces the smallest result value.

Output: result mod 10000027.

Example Input

....o.
.o....
...o..
.....o
...o..
..o...

Example Walkthrough

Initial board:

....o. -> row 0, queen at col 4 .o.... -> row 1, queen at col 1 ...o.. -> row 2, queen at col 3 .....o -> row 3, queen at col 5 ...o.. -> row 4, queen at col 3 ..o... -> row 5, queen at col 2

The optimal target (a valid 6-queens arrangement that achieves minimum cost):

....o. -> row 0, col 4 ..o... -> row 1, col 2 o..... -> row 2, col 0 .....o -> row 3, col 5 ...o.. -> row 4, col 3 .o.... -> row 5, col 1

Movement costs (in this example, each queen happens to stay in its original row):

Queen at (0, 4) ends at (0, 4). Cost 0 (Same cell) Queen at (1, 1) ends at (1, 2). Cost 1 (Same row, one slide) Queen at (2, 3) ends at (2, 0). Cost 1 (Same row, one slide) Queen at (3, 5) ends at (3, 5). Cost 0 (Same cell) Queen at (4, 3) ends at (4, 3). Cost 0 (Same cell) Queen at (5, 2) ends at (5, 1). Cost 1 (Same row, one slide)

Total cost C = 3. Target columns: [4, 2, 0, 5, 3, 1].

result = 4 * 3^0 + 2 * 3^2 + 0 * 3^3 + 5 * 3^4 + 3 * 3^5 + 1 * 3^6 result = 4 * 1 + 2 * 9 + 0 * 27 + 5 * 81 + 3 * 243 + 1 * 729 result = 4 + 18 + 0 + 405 + 729 + 729 = 1885

1885 mod 10000027 = 1885

What is the encoded result (mod 10000027) for the optimal rearrangement?