Roads
Национална Олимпиада по Информатика 2012, Контролно 2
Time Limit: 0.1s, Memory Limit: 64MiB
След един дълъг ден, в спасяване на принцове от ламята, Ели най-накрая заспа. И докато в реалния живот нищо не може да я уплаши, в сънищата й я гонят страшните зверове от изминалия ден.

Всъщност кошмарите й винаги са доста идентични – в нейния любим замък я гони дракон, като тя в началото се намира на една и съща позиция в него и иска да стигне до изхода по възможно най-бърз начин. Ели, както казахме, често сънува този сън, затова иска да заблуди гонещия й дракон, като всеки път избира различен най-къс път до изхода. Помогнете й, като по дадена карта на замъка, къде се намира Ели и къде се намира изходът определите колко на брой различни най-къси пътища съществуват.

Замъка можем да представим като матрица с N реда и M колони, някои от които са непроходими (стени, статуи, стаи, в които звучат песни на Justin Bieber), които ще отбелязваме с '#', а други са свободни – тях ще отбелязваме с '.'. В точно една клетка ще се намира Ели, която ще отбележим с 'E', и точно една друга клетка ще бъде изходът, който ще отбележим с 'X'. В един ход Ели може да се придвижи в някоя от четирите съседни по вертикала или хоризонтала клетки (където има такива).

По зададена карта на замъка определете броя различни пътища между Ели и изхода с минимална дължина. Два пътя се считат за различни, ако в някой от ходовете Ели се придвижва в една посока в единия и в друга посока в другия.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и M – съответно броя редове и броя колони, които има картата на замъка. На всеки от следващите N реда ще има по M символа, описващи замъка. Всеки от тези символи ще е '.', '#', 'E' или 'X'.
Изход
На стандартния изход изведете едно единствено число – броя различни най-къси пътища от Ели до изхода, които не преминават през непроходима клетка. Тъй като това число може да е много голямо, от Вас се иска да изведете само неговия остатък при деление на 1,000,000,007.
Ограничения
  • 1 ≤ N, M ≤ 100
Примерен Вход Примерен Изход
4 5 ..... E##.. .#..X ....# 5
Най-краткият път от Ели до изхода е с дължина 7. Петте възможни пътя са: "URRRRDD", "URRRDRD", "URRRDDR", "DDRRURR", "DDRRRUR". Тук с 'U' означаваме ход нагоре, с 'D' надолу, с 'R' надясно и с 'L' наляво.
Мрън!