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