Atentie
Argintolac și Bronzolac concurează într-un joc pe o tablă cu N
linii și M
coloane care conține obstacole.
Jocul se desfășoară în următorul fel:
S
ce conține doar literele 'U
', 'D
', 'L
', 'R
'.S
.i
în celula adiacentă din direcția reprezentată de caracterul \(S_i\) ('U
' - în sus, 'D
' - în jos, 'L
' - în stânga, 'R
' - în dreapta).Înainte de începerea jocului, dealerul Nitsoc primește o atenție de la Argintolac și se întreabă care este numărul de șiruri S
pe care le poate alege inițial astfel încât Argintolac să câștige. Fiind foarte competitivi, atât Argintolac, cât și Bronzolac joacă optim. Din moment ce Nitsoc și-a petrecut ultimii 5 ani la Master...Club, el nu este capabil să rezolve problema singur așa că vă cere ajutorul. Să se afișeze răspunsul modulo \(10^9 + 7\).
Pe primul rând se găsesc 2 numere întregi pozitive N s
și M
, reprezentând numărul de linii, respectiv numărul de coloane al tablei.
Pe următoarele N
linii este descrisă configurația tablei, linia i
conținând M
caractere de tipul '.
' (reprezentând o celulă liberă) sau '#
' (reprezentând o celulă ce conține un obstacol).
Se va afișa pe primul rând un număr întreg reprezentând numărul de șiruri nevide S
care pot fi alese inițial astfel încât Argintolac să câștige, modulo \(10^9 + 7\).
1 ≤ N,M ≤ 2000
N = 1
1 ≤ N,M ≤ 3
1 ≤ N,M ≤ 10
1 ≤ N,M ≤ 50
1 ≤ N,M ≤ 150
1 ≤ N,M ≤ 1000
stdin
2 4
##..
.##.
stdout
4
stdin
2 2
..
..
stdout
12
stdin
4 4
....
.#..
....
#...
stdout
148
ID: 59
Upload: liviu
Input: Console Input
Memory limit: 64MB/16MB
Time limit: 0.2s
Author: Costin Andrei Oncescu, Andrei Constantinescu
Source: InfoPro Runda 4 Grupa A