EduBrick

Развозка по кварталам

8000 мс · 128 МБ · всё или ничего

Город расчерчен на кварталы n×mn \times m. Курьер выезжает из левого верхнего квартала и едет в правый нижний, за один переезд перемещаясь в соседний квартал вправо или вниз.

Некоторые кварталы перекрыты, въезжать в них нельзя. Сколько существует различных маршрутов? Ответ по модулю 109+710^9 + 7. Начальный и конечный кварталы не перекрыты.

Формат ввода

В первой строке числа nn и mm от 11 до 20002000. В следующих nn строках по mm символов: точка — свободно, решётка — перекрыто.

Формат вывода

Одно число.

Примеры

ввод
1 1
.
вывод
1
Войдите, чтобы отправлять решения.