У нас є сітка з ~H~ горизонтальними рядками і ~W~ вертикальними стовпцями клітин. Клітина (~i,j~) знаходиться в ~i~-му рядку зверху та ~j~-му стовпці зліва, є стіною, якщо ~S_{ij}~ дорівнює #, і дорогою, якщо ~S_{ij }~ є '.'. У клітині (1, 1) стоїть ферзь, шахова фігура. За один рух він може переміщати будь-яку кількість квадратів праворуч, вниз або по діагоналі в нижній правий бік по вільних клітинах, не перестрибуючи через стіни.

Скількома способами ферзь може пройти від клітини (1, 1) до клітини (~H, W~)?

Знайдіть кількість за модулем (~10^9 + 7~).

Тут два шляхи переміщення вважаються різними тоді і тільки тоді, коли існує ~i~ такий, що положення ферзя після ~i~-го ходу різне в цих двох шляхах.

Формат вхідних даних

Перший рядок містить цілі числа ~H, W~ (~2 \le N \le 2000~)

Наступні  ~N~ рядків містять ~S_{ij}~ (~S_{ij}~ = '.', '#', ~S_{11}=S_{HW}='.'~)

Формат вихідних даних

У вихідний потік виведіть шукану кількість шляхів.

Примітка

До прикладу 1:

Існує 10 шляхів, а саме:

• (1,1)→(1,2)→(1,3)→(2,3)→(3,3)

• (1,1)→(1,2)→(1,3)→(3,3)

• (1,1)→(1,2)→(2,3)→(3,3)

• (1,1)→(1,3)→(2,3)→(3,3)

• (1,1)→(1,3)→(3,3)

• (1,1)→(2,1)→(3,1)→(3,2)→(3,3)

• (1,1)→(2,1)→(3,1)→(3,3)

• (1,1)→(2,1)→(3,2)→(3,3)

• (1,1)→(3,1)→(3,2)→(3,3)

• (1,1)→(3,1)→(3,3)

Приклад вхідних даних

3 3
...
.#.
...

Приклад вихідних даних

10

Приклад вхідних даних

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

Приклад вихідних даних

84

Приклад вхідних даних

8 10
..........
..........
..........
..........
..........
..........
..........
..........

Приклад вихідних даних

13701937