This page is still under construction.

Parts of this page are still being built. What you see may change.

Autumn Park

Time limit2sMemory limit512 MB

Summary
On a grid with obstacles, count paths from entrance to exit whose length is exactly two more than the shortest path, modulo 1e9+9.
Level

Medium7 of 10

Topics
Graph, BFS, Dynamic programming, Combinatorics
Solved
No attempts yet

Problem

Sunday morning. Time for the olympiad. Veniamin took a stack of blank paper, a pen, a couple of sandwiches (what else would he need?) and opened a map site to see where and how he should get there. What luck! There is a lovely park on the way, and Veniamin happens to enjoy walking through parks. The park is a rectangular field divided into square cells, each of which is either a lawn with paths or some obstacle (thickets of bushes, trees, or even a fenced-off monument).

Veniamin has to arrive at the olympiad on time, so he cannot afford to wander around the park for long. Moving between two cells that share a side takes one second. Veniamin cannot stand still, so every second he moves to some neighboring cell. Veniamin decided he could afford to walk two extra seconds. Your task is to count the number of ways to cross the park such that the walking time is exactly two seconds more than the minimum.

The entrance to the park and the exit from it are some distinct marked cells in the park; leaving the park is forbidden, and movement is allowed only between cells that share an edge. Veniamin must walk two seconds longer than the optimal time from the entrance to the exit, so he may visit the entrance or the exit as an intermediate point of the path. Since the answer can be quite large, you must output the number of paths modulo 109+910^9 + 9.

Input

The first line of the input contains two numbers hh and ww: the dimensions of the park. The following hh lines contain ww characters each. The character <<.>> means that the corresponding cell is a path or lawn that can be walked on. The character <<\#>> means an obstacle. The characters <<E>> and <<X>> mean the entrance to the park and the exit from it, respectively.

Constraints: 1≤h≤5001 \le h \le 500, 1≤w≤5001 \le w \le 500; the characters <<E>> and <<X>> each occur exactly once in the input. Note that the entrance and exit are not necessarily on the boundary of the park: for example, the entrance cell could be a subway lobby located in the park, from which Veniamin is going to come out on his way.

Output

Output a single number: the number of paths that are exactly two seconds longer than the shortest one. If the park is arranged so that it is impossible to get from the entrance to the exit, output zero.

Examples1

  1. Example 1

    Input
    6 9
.........
..######X
..#......
.E..####.
..##...#.
.....#...
    Expected output
    15