가을 공원

일요일 아침. 올림피아드에 갈 시간이다. 베니아민은 빈 종이 묶음, 펜, 샌드위치 두 개를 챙겼다. 또 뭐가 필요할까. 그리고는 지도 사이트를 열어 어떻게, 어디로 가야 하는지 확인했다. 운이 좋다! 가는 길에 멋진 공원이 있고, 베니아민은 공원 산책을 좋아한다. 공원은 정사각형 칸으로 나뉜 직사각형 모양의 땅이며, 각 칸은 산책로가 있는 잔디밭이거나 장애물(덤불, 나무, 혹은 울타리로 둘러싸인 기념비)이다.

올림피아드에 제때 도착해야 하므로 베니아민은 공원을 오래 거닐 수 없다. 공원에서 변을 맞댄 두 인접 칸 사이를 이동하는 데 1초가 걸린다. 베니아민은 제자리에 서 있을 수 없어서 매초 인접한 칸으로 이동한다. 베니아민은 2초를 더 산책해도 괜찮다고 생각했다. 여러분의 과제는 공원을 통과하는 경로 중 산책 시간이 최소 시간보다 정확히 2초 더 긴 경로의 수를 세는 것이다.

공원의 입구와 출구는 공원 안의 서로 다른 특정 칸이다. 공원 밖으로 나갈 수 없고, 변을 맞댄 인접 칸 사이로만 이동할 수 있다. 베니아민은 입구에서 출구까지 가는 최적 시간보다 2초 더 오래 걸어야 하므로, 중간 지점으로 입구나 출구에 다시 들를 수 있다. 답이 클 수 있으므로 경로 수를 $10^9 + 9$로 나눈 나머지를 구한다.

첫째 줄에 공원의 크기 $h$와 $w$가 주어진다. 다음 $h$개 줄에는 각각 $w$개 문자가 주어진다. 문자 <<.>>은 해당 칸이 걸어 다닐 수 있는 산책로나 잔디밭임을 뜻한다. 문자 <<\#>>은 장애물을 뜻한다. 문자 <<E>>와 <<X>>는 각각 공원의 입구와 출구를 뜻한다.

제약: $1 \le h \le 500$, $1 \le w \le 500$. 문자 <<E>>와 <<X>>는 입력에 각각 정확히 한 번씩 나타난다. 입구와 출구가 반드시 공원의 경계에 있는 것은 아니다. 예를 들어 입구 칸은 공원 안에 있는 지하철역 대합실일 수 있으며, 베니아민은 그곳에서 나와 길을 떠난다.

최단 경로보다 정확히 2초 더 긴 경로의 수를 한 줄에 출력한다. 입구에서 출구로 갈 수 없다면 0을 출력한다.