Tu tarea consiste en crear una cuadrícula de ~n \times n~ donde cada fila y columna contenga exactamente una ~A~ y una ~B~. Algunos caracteres ya están colocados. ¿De cuántas maneras se puede completar la cuadrícula?

Entrada

La primera línea de entrada contiene un entero ~n~: el tamaño de la cuadrícula.

A continuación, hay ~n~ líneas que describen la cuadrícula. Cada línea contiene ~n~ caracteres: el punto (.) representa un cuadrado vacío, y ~A~ y ~B~ indican los caracteres ya colocados.

Puedes asumir que cada fila y columna contiene como máximo una ~A~ y una ~B~.

Salida

Imprime un entero: el número de maneras módulo ~10^9+7~.

Restricciones

• ~2 \leq n \leq 500~

Ejemplo de Entrada

5
.....
..AB.
.....
B....
...A.

Ejemplo de Salida

16