У нас є сітка з \(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