Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Ruudukko

Ruudukko


View task | Model solution | Statistics


Ruudukko

Time limit:1.00 s
Memory limit:128 MB

Sinulle on annettu $n \times m$ -kokoinen ruudukko, jonka jokainen ruutu on lattiaa tai seinää. Tehtäväsi on kulkea ruudukon vasemmasta yläkulmasta oikeaan alakulmaan lattiaa pitkin. Saat liikkua joka siirrolla askeleen oikealle tai alaspäin.

Montako kuvatun kaltaista reittiä on olemassa?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluvut $n$ ja $m$: ruudukon koko.

Tämän jälkeen syötteessä on ruudukon kuvaus. Jokainen ruutu on lattiaa (.) tai seinää (*).

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: reittien määrä modulo $10^9+7$.

Rajat
Esimerkki

Syöte:
3 4
....
.*.*
....


Tuloste:
2