Осінній парк#6287
Неділя, ранок. Час йти на олімпіаду. Веніамін взяв пачку чистих аркушів, ручку, кілька бутербродів — що ще може знадобитися? — і відкрив картографічний сайт, щоб дізнатись, куди і як добиратися. Яка удача! На шляху є чудовий парк, а Веніамін якраз любить прогулюватись парками.
Парк — це прямокутне поле, поділене на квадратні клітини, у кожній з яких або газон з доріжками, або якась перешкода (зарості, дерева, а то й навіть огороджений пам'ятник).
Веніамін має прийти на олімпіаду вчасно, тому не може дозволити собі довго затримуватися у парку. Переміщення між двома суміжними по стороні клітинами парку триває одну секунду. Веніамін не може стояти на місці, тому щосекунди переходить у суміжну клітину. Він вирішив, що може дозволити собі прогулятись на дві секунди довше за мінімальний шлях. Ваше завдання — підрахувати кількість способів пройти через парк так, щоб час прогулянки був рівно на дві секунди більший за мінімальний.
Вхід у парк і вихід з нього — це певні спеціально позначені, різні клітини парку; виходити за межі парку заборонено. Пересуватись можна лише між суміжними по ребру клітинами. Веніамін повинен прогулюватися на дві секунди довше за оптимальний час проходу від входу до виходу, і під час шляху він може ще раз потрапити у вхід чи вихід. Оскільки відповідь може бути великою, виведіть залишок від ділення кількості шляхів на 10^9+9.
У першому рядку вхідного файлу задано два числа і — розміри парку. Наступні рядків містять по символів у кожному. Символ "." означає, що у відповідній клітині доріжка або газон, якими можна ходити. Символ "#" означає перешкоду. Символи "E" і "X" позначають вхід до парку та вихід з нього відповідно.
Обмеження: 1 \leq h \leq 500, 1 \leq w \leq 500. Символи "E" і "X" зустрічаються у вхідних даних рівно по одному разу. Зверніть увагу, що вхід і вихід не обов'язково знаходяться на межі парку: наприклад, входом може бути розташований у парку вестибюль метро.
У вихідний файл виведіть одне число: кількість шляхів, які довші від найкоротшого рівно на дві секунди. Якщо дістатися від входу до виходу неможливо, виведіть нуль.
Приклад 1