Пути мимо стен
8000 мс · 256 МБ · всё или ничего
То же поле, но некоторые клетки — стены, вставать на них нельзя.
Сколько существует путей из левой верхней клетки в правую нижнюю? Ответ по модулю . Обе угловые клетки свободны.
Формат ввода
В первой строке числа и от до . В следующих строках по символов: точка — свободно, решётка — стена.
Формат вывода
Одно число.
Примеры
ввод
1 1 .
вывод
1
Примечание
Стена — это состояние, в которое нельзя попасть: оставьте у неё ноль путей. Осторожно с первой строкой и первым столбцом: там путей не всегда один — за стеной их ноль.
Войдите, чтобы отправлять решения.