문자열 배열

시간 제한2초메모리 제한512 MB

요약

길이 1 이상 W 이하인 문자열 S가 주어진 위치에서 배열 X를 채울 때 주어진 조각 F와 일치하는 경우의 수를 구한다.

난이도: 어려움10점 중 8점
유형: 문자열 매칭, 정수론, 수학
정답자: 아직 제출이 없습니다

문제

영선이는 행이 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로 나눈 나머지를 출력한다.

예제3

예제 1
입력
```
2 3 7 1 1
dea
abc
```
예상 출력
```
1
```
예제 2
입력
```
1 5 6 1 0
xyxxy
```
예상 출력
```
28
```
예제 3
입력
```
3 6 6 0 0
gogogo
jijiji
rarara
```
예상 출력
```
0
```