욱제는 사과팬이야!!

욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달하려고 한다. 며칠간 관찰한 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다.

구사과가 있는 곳은 N×M 크기의 직사각형 지도로 나타낼 수 있으며, 1×1 크기의 정사각형으로 나누어져 있다. 구사과의 위치는 (i, j)로 나타낼 수 있으며, (i, j)는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸을 의미한다.

지도의 각 칸에는 E, S, B 중 하나의 문자가 쓰여 있는데, 구사과는 이 문자를 보고 이동한다. 구사과가 (i, j)에 있을 때 그 칸에 E가 쓰여 있으면 (i, j+1)로, S가 쓰여 있으면 (i+1, j)로, B가 쓰여 있으면 (i, j+1) 또는 (i+1, j)로 순간이동한다. 구사과는 지치지 않으므로 계속 이동한다.

욱제는 구사과의 위치를 모르지만, 구사과가 어디에서 이동을 시작하든 최종 목적지는 항상 (N, M)이라는 사실을 알고 있다. 욱제는 (N, M)에 선물을 놓아 구사과가 항상 선물을 가져가게 하려고 한다. 구사과가 선물을 가져가는 경로의 수를 구하는 프로그램을 작성하시오. 선물이 놓인 칸으로 구사과가 이동하면 구사과는 항상 선물을 가져간다.

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 3,000)

둘째 줄부터 N개의 줄에 걸쳐 구사과가 있는 곳의 지도가 주어진다. (N, M)에는 도착지임을 뜻하는 X가 주어진다.

지도에 쓰여 있는 대로 이동했을 때 지도를 벗어나는 경우는 없다.

첫째 줄에 구사과가 선물을 가져가는 경로의 수를 출력한다. 경로가 너무 많아질 수 있으므로 1,000,000,009 (10^9 + 9)로 나눈 나머지를 출력한다.