E. Rock Is Push
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы находитесь в левой верхней клетке $$$(1, 1)$$$ лабиринта размера $$$n \times m$$$ клеток. Ваша цель — попасть в правую нижнюю клетку $$$(n, m)$$$. Вы можете двигаться только вправо и вниз по одной клетке за ход. Переход вправо из клетки $$$(x, y)$$$ ведёт в клетку $$$(x, y + 1)$$$, а переход вниз — в клетку $$$(x + 1, y)$$$.

В некоторых клетках лабиринта лежат камни. Когда вы перемещаетесь в клетку с камнем, камень сдвигается в следующую клетку по направлению движения. Если в следующей клетке также есть камень, он сдвигается дальше в том же направлении, и так далее.

Лабиринт окружён непроницаемыми стенами, поэтому ходы, в результате которых вы или камень выходят за границы лабиринта, невозможны.

Вычислите количество различных способов добраться от старта до цели по модулю $$$10^9 + 7$$$. Два способа считаются различными, если существует клетка, посещённая в одном из способов, но не посещённая в другом.

Входные данные

В первой строке записано два целых числа $$$n, m$$$ — размеры лабиринта ($$$1 \leq n, m \leq 2000$$$).

Следующие $$$n$$$ строк описывают лабиринт. Каждая из этих строк содержит $$$m$$$ символов. $$$j$$$-й символ $$$i$$$-й из этих строк равен «R», если клетка $$$(i, j)$$$ содержит камень, или «.», если клетка $$$(i, j)$$$ пуста.

Гарантируется, что стартовая клетка $$$(1, 1)$$$ пуста.

Выходные данные

Выведите одно целое число — количество различных способов добраться из клетки $$$(1, 1)$$$ в клетку $$$(n, m)$$$ по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
1 1
.
Выходные данные
1
Входные данные
2 3
...
..R
Выходные данные
0
Входные данные
4 4
...R
.RR.
.RR.
R...
Выходные данные
4
Примечание

В первом примере нам нельзя (и не нужно) двигаться, поэтому единственный способ добраться посещает единственную клетку $$$(1, 1)$$$.

Во втором примере цель заблокирована и в неё нельзя попасть.

Иллюстрации к третьему примеру можно найти здесь: https://assets.codeforces.com/rounds/1225/index.html