Considera una cuadrícula de \(N \times N\) cuyas casillas pueden tener trampas. No está permitido moverse a una casilla con una trampa.

Tu tarea es calcular el número de caminos desde la casilla superior izquierda hasta la casilla inferior derecha. Solo puedes moverte hacia la derecha o hacia abajo.

Entrada

La primera línea de entrada tiene un número entero \(N\): el tamaño de la cuadrícula (\(1 \leq N \leq 1000\)).

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

Imprime el número de caminos módulo \(10^9 + 7\).

Ejemplo

Entrada:

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

Salida:

3