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