Autumn Park
Sunday morning marks the time for the olympiad. Veniamin gathers his essentials: a pack of blank paper, a pen, and a couple of sandwiches. Ready to go, he checks a mapping site to plan his route. To his delight, there's a beautiful park along the way, and Veniamin enjoys strolling through parks. This park is a rectangular field divided into square cells, each either a walkable lawn or an obstacle like bushes, trees, or a fenced monument.
Veniamin must reach the olympiad on time, so he can't linger in the park for too long. Moving between two adjacent cells takes one second, and Veniamin must keep moving every second. He decides he can spare an extra two seconds for his walk. Your task is to determine the number of ways he can traverse the park such that his walk is exactly two seconds longer than the shortest possible path.
The park has designated entrance and exit cells, and Veniamin cannot leave the park's boundaries. Movement is restricted to edge-adjacent cells. Veniamin's path must be two seconds longer than the shortest path from entrance to exit, and he may revisit the entrance or exit during his walk. Since the number of possible paths can be large, provide the result as the remainder when divided by (10^9+9).
Input
The first line of the input contains two numbers, h and w, representing the park's dimensions. The following h lines each contain w characters. A "." indicates a walkable path or lawn, while a "#" represents an obstacle. The characters "E" and "X" denote the entrance and exit of the park, respectively.
Constraints: 1 ≤ h ≤ 500, 1 ≤ w ≤ 500. The characters "E" and "X" appear exactly once in the input. Note that the entrance and exit are not necessarily on the park's boundary; for instance, the entrance might be a subway vestibule within the park.
Output
Output a single number: the count of paths that are exactly two seconds longer than the shortest path. If it's impossible to reach the exit from the entrance, output zero.