문자열 배열

영선이는 행이 10,000개이고 열이 W개인 배열 X에 문자를 채우려고 한다.

배열을 채우기 전에 길이가 1 이상 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개인 조각 F가 주어진다. F의 왼쪽 위 칸은 X에서 행 $i_0$, 열 $j_0$에 놓인다. 즉 모든 $i$, $j$에 대해 $F[i][j] = X[i_0+i][j_0+j]$이다. 위 알고리즘으로 채운 X가 이 위치에서 F와 일치하도록 만드는 문자열 S의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 F의 행의 개수 N, F의 열의 개수 M, X의 열의 개수 W, F의 왼쪽 위 칸이 놓인 행 번호 $i_0$과 열 번호 $j_0$이 주어진다. ($1 \le N, M \le 10$, $M \le W \le 10000$, $0 \le i_0 \le 10000 - N$, $0 \le j_0 \le W - M$)

둘째 줄부터 N개 줄에 걸쳐 F가 주어진다. 각 줄은 알파벳 소문자 M개로 이루어진다.

첫째 줄에 조건을 만족하는 문자열 S의 개수를 1,000,000,009로 나눈 나머지를 출력한다.