14253번 - 문자열 배열

영선이는 행의 크기가 10,000, 열의 크기가 W인 배열 X를 가지고 있고, 이 배열을 문자로 채우려고 한다.

배열을 채우기 위해서는 먼저 크기가 최대 W인 문자열 S를 하나 정해야 한다. 이때, S는 알파벳 소문자로만 이루어져 있다.

배열을 채우는 알고리즘은 다음과 같다.

cur = 0
for (int i=0; i<10000; i++) {
    for (int j=0; j<W; j++) {
        X[i][j] = s[cur];
        cur = (cur + 1) % S.length();
    }
}

행의 크기가 N, 열의 크기가 M인 배열 X의 일부분 F가 주어진다. F의 가장 왼쪽 윗 행은 X에서는 i0, 열은 j0이다. 즉, F[i][j]는 X[i0+i][j0+j]와 같다. 주어진 F를 부분 배열로 갖는 배열 X를 만들 수 있는 문자열 S의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 F의 크기 N, M과 X의 열의 크기 W, F의 가장 왼쪽 윗 행 i0과 열 j0이 주어진다. (1 ≤ N, M ≤ 10, M ≤ W ≤ 10,000, 0 ≤ i0 ≤ 10,000-N, 0 ≤ j0 ≤ W-M)

둘째 줄부터 N개의 줄에는 F가 주어진다.

첫째 줄에 입력으로 주어진 F를 부분 배열로 갖는 X를 만드는 문자열 S의 개수를 1,000,000,009로 나눈 나머지를 출력한다.