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:

• Dealerul Nitsoc alege un șir nevid de caractere S ce conține doar literele 'U', 'D', 'L', 'R'.
• Argintolac alege o celulă liberă (care nu conține vreun obstacol) a tablei și plasează un robot în aceasta.
• Bronzolac reordonează (sau nu) caracterele șirului S.
• Robotul parcurge traseul descris de șirul dat de Bronzolac, deplasându-se la pasul 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).
• Argintolac câștigă dacă robotul ajunge teafăr în celula finală (acesta nu iese de pe tablă și nu se lovește de niciun obstacol pe parcurs), altfel, Bronzolac câștigă.

Î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\).

Date de intrare

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).

Date de ieșire

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\).

Restricții

• 1 ≤ N,M ≤ 2000
• Tabla conține cel puțin o celulă liberă.

Subtask 1 (29 puncte)

• N = 1

Subtask 2 (8 puncte)

• 1 ≤ N,M ≤ 3

Subtask 3 (13 puncte)

• 1 ≤ N,M ≤ 10

Subtask 4 (9 puncte)

• 1 ≤ N,M ≤ 50

Subtask 5 (11 puncte)

• 1 ≤ N,M ≤ 150

Subtask 6 (16 puncte)

• 1 ≤ N,M ≤ 1000

Subtask 7 (14 puncte)

• Fără restricții suplimentare

Exemple

stdin

2 4
##..
.##.

stdout

4

stdin

2 2
..
..

stdout

12

stdin

4 4
....
.#..
....
#...

stdout

148