Considere una cuadrícula de ~n \times n~ cuyos cuadrados pueden tener trampas. No se permite moverse a un cuadrado con una trampa. Su tarea es calcular el número de caminos desde el cuadrado superior izquierdo hasta el cuadrado inferior derecho. Solo puede moverse hacia la derecha o hacia abajo.

Entrada

La primera línea de entrada tiene un entero ~n~: el tamaño de la cuadrícula. Después de esto, hay ~n~ líneas que describen la cuadrícula. Cada línea tiene ~n~ caracteres: . denota una celda vacía y * denota una trampa.

Salida

Imprima el número de caminos módulo ~10^9+7~.

Restricciones

• ~1 \leq n \leq 1000~

Ejemplo de Entrada

4
....
.*..
...*
*...

Ejemplo de Salida

3