Grid Paths I.

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, ~~Swift~~, TCL, Text, Turing, VB, Zig

Considere una cuadrícula de $n \times n$ ~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$ ~n~: el tamaño de la cuadrícula. Después de esto, hay $n$ ~n~ líneas que describen la cuadrícula. Cada línea tiene $n$ ~n~ caracteres: . denota una celda vacía y * denota una trampa.

Salida

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

Restricciones

$1 \leq n \leq 1000$ ~1 \leq n \leq 1000~

Ejemplo de Entrada

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

Ejemplo de Salida

Comments

There are no comments at the moment.