| Автор: | Г. Корнеев, О. Давыдов, В. Аксёнов (Жюри XXI командной олимпиады школьников СПб по информатике) | Ограничение времени: | 2 сек | |
| Входной файл: | park.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | park.out |
Воскресенье, утро. Пора на олимпиаду. Вениамин взял пачку чистой бумаги, ручку, пару бутербродов — что еще понадобится? — и открыл картографический сайт чтобы посмотреть, куда и как ему добираться. Какая удача! На пути есть прекрасный парк, а Вениамин как раз любит гулять по паркам. Парк представляет собой прямоугольное поле, разбитое на квадратные клеточки, в каждой из которых либо газон с дорожками, либо какое-то препятствие (заросли кустарника, деревья, а то и вовсе какой-нибудь огороженный памятник).
На олимпиаду нужно прийти вовремя, так что Вениамин не может позволить себе долго разгуливать по парку. Перемещение между двумя соседними по стороне клеточками парка занимает одну секунду. Вениамин не может устоять на месте, поэтому каждую секунду он перемещается в какую-либо соседнюю клеточку. Вениамин решил, что может позволить себе гулять лишние две секунды. Ваша задача: посчитать количество способов пройти через парк так, чтобы время прогулки было ровно на две секунды больше минимального.
Вход в парк и выход из него — это некоторые выделенные различные клетки в парке, выходить за пределы парка запрещается, передвигаться можно только между соседними по ребру клетками. Вениамин должен гулять на две секунды дольше оптимального времени прохода от входа к выходу, поэтому он может в качестве промежуточной точки пути оказаться на входе или выходе. Поскольку ответ на задачу может быть довольно большим, от вас требуется остаток от деления количества путей на 109 + 9.
В первой строке входного файла заданы два числа h и w: размеры парка. Следующие h~строк содержат по w~символов в каждой. Символ "." означает, что в соответствующей клетке дорожка или газон, по которому можно ходить. Символ "#" означает препятствие. Символы "E" и "X" означают вход в парк и выход из него соответственно.
Ограничения: 1 ≤ h ≤ 500, 1 ≤ w ≤ 500, символы "E" и "X" встречаются во входном файле ровно по одному разу. Обратите внимание, что вход и выход не обязательно находятся на границе парка: например, клеткой входа может быть расположенный в парке вестибюль метро, из которого Вениамин собирается выходить на своем пути.
В выходной файл выведите одно число: количество путей, которые длиннее кратчайшего ровно на две секунды. Если парк устроен так, что невозможно добраться от входа до выхода, то выведите ноль.
| № | Входной файл (park.in) |
Выходной файл (park.out) |
|---|---|---|
| 1 |
|
|