9467번 - 문자열 경로

N × M 크기의 직사각형 격자가 있다. 각 격자에는 알파벳 대문자가 하나씩 적혀있다. 각 행의 위 1번부터 아래 N번까지 번호가 연속되게 매겨져 있고, 각 열은 왼쪽 1번부터 오른쪽 M번까지 번호가 연속되게 매겨져 있다. (1,1)부터 시작해서 (N,M)까지 아래 혹은 오른쪽으로 이동해서 도달할 수 있다. 이때, 방문한 격자에 쓰여 있는 문자를 빠짐없이 순서대로 나열한 것을 문자열 경로라 한다.

길이가 N+M-1인 서로 다른 문자열 두 개가 주어졌을 때, 두 문자열 모두 문자열 경로가 될 수 있는 직사각형 격자의 개수를 구하는 프로그램을 작성하시오. 이때, 답이 커질 수 있으므로, 1,000,000,009로 나눈 나머지를 출력한다.

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

두 번째, 세 번째 줄에 알파벳 대문자로 이루어진 길이가 N+M-1인 문자열이 주어진다.

주어진 두 문자열을 경로로 할 수 있는 직사각형 격자의 개수를 출력한다.

위와 같이 두 가지가 가능하다.