L. Lexica
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Lexica puzzle consists of a square grid divided into $$$n \times n$$$ cells. Some cells are active, while others are not, with all active cells forming a crossword grid. Letter pieces are placed along the edges of the square. The pieces on the left and right edges can be moved to active cells in the same row, while the pieces on the top and bottom edges can be moved to active cells in the same column. It is not allowed to place two pieces in the same active cell. The number of pieces is equal to the number of active cells. The goal of the game is to move all pieces to the active cells so that a valid crossword grid is formed. This state of the game is referred to as a solution.

For instance, the initial state of the puzzle and its solution are shown in the following illustration:

You are given a Lexica puzzle. It is known that on any two pieces, one of which can be moved horizontally and the other vertically, the letters are different. Your task is to count the number of distinct solutions to the puzzle. Two solutions are considered distinct if there exists at least one active cell where the corresponding solutions have differing letters.

Input

The first line contains the integer $$$n$$$ ($$$4 \le n \le 13$$$). The following $$$(n+2)$$$ lines provide the description of the puzzle. Each line consists of exactly $$$(n+2)$$$ characters. Active cells are represented by the symbol ".", pieces are represented by uppercase Latin letters, and all other cells are represented by the symbol "#". Please refer to the example for a clearer understanding.

Output

Output a single integer — the number of distinct solutions.

Example
Input
5
##ARRR#
H.#.##S
Y.....E
O.#.#.E
##....E
###.#.E
#XNT#A#
Output
768