문자열 경로

$N \times M$ 크기의 직사각형 격자가 있다. 각 칸에는 알파벳 대문자가 하나씩 적혀 있다. 행 번호는 위에서 아래로 1번부터 $N$번까지, 열 번호는 왼쪽에서 오른쪽으로 1번부터 $M$번까지 붙어 있다.

$(1, 1)$에서 출발해 한 번에 아래쪽이나 오른쪽으로 한 칸씩 움직여 $(N, M)$에 도착하는 경로를 생각하자. 지나간 칸에 적힌 문자를 지나간 순서대로 빠짐없이 이어 붙이면 길이가 $N+M-1$인 문자열이 되고, 이 문자열을 그 격자의 문자열 경로라고 한다. 경로를 어떻게 잡느냐에 따라 격자 하나에서 문자열 경로가 여러 개 나오기도 한다.

길이가 $N+M-1$인 서로 다른 문자열 두 개가 주어진다. 두 문자열이 모두 문자열 경로가 되는 직사각형 격자가 몇 개인지 세는 프로그램을 작성하시오. 같은 자리의 칸에 적힌 문자가 하나라도 다르면 두 격자는 서로 다른 것으로 센다. 답이 커질 수 있으므로 1,000,000,009로 나눈 나머지를 출력한다.

첫째 줄에 두 자연수 $N$과 $M$이 주어진다. ($1 \le N, M \le 8$)

둘째 줄과 셋째 줄에 알파벳 대문자로 이루어진 길이 $N+M-1$인 문자열이 한 줄에 하나씩 주어진다. 두 문자열은 서로 다르다.

주어진 두 문자열이 모두 문자열 경로가 되는 직사각형 격자의 개수를 1,000,000,009로 나눈 나머지를 출력한다.

$N = 2$, $M = 2$이고 두 문자열이 ABC와 ADC일 때, 아래 두 격자가 조건을 만족한다.