← вернуться к уроку · Итоговый контест: второй тур
Развозка по кварталам
8000 мс · 128 МБ · всё или ничего
Город расчерчен на кварталы . Курьер выезжает из левого верхнего квартала и едет в правый нижний, за один переезд перемещаясь в соседний квартал вправо или вниз.
Некоторые кварталы перекрыты, въезжать в них нельзя. Сколько существует различных маршрутов? Ответ по модулю . Начальный и конечный кварталы не перекрыты.
Формат ввода
В первой строке числа и от до . В следующих строках по символов: точка — свободно, решётка — перекрыто.
Формат вывода
Одно число.
Примеры
ввод
1 1 .
вывод
1
Войдите, чтобы отправлять решения.