EduBrick
← вернуться к уроку · Динамика по сетке

Пути мимо стен

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

То же поле, но некоторые клетки — стены, вставать на них нельзя.

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

Формат ввода

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

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

Одно число.

Примеры

ввод
1 1
.
вывод
1

Примечание

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

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