String array

Time limit2sMemory limit512 MB

Summary

Count strings S of length 1 to W such that the repeated periodic filling of X matches the given patch F at the fixed offset.

Level: Hard8 of 10
Topics: String matching, Number theory, Math
Solved: No attempts yet

Problem

Yeongseon wants to fill an array X with letters. X has 10,000 rows and W columns.

Before filling it she picks one string S whose length is at least 1 and at most W. S consists of lowercase letters only.

The filling algorithm is the following.

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();
    }
}

You are given a patch F with N rows and M columns. The top left cell of F sits in row $i_0$ and column $j_0$ of X, so $F[i][j] = X[i_0+i][j_0+j]$ holds for every $i$ and $j$ . Write a program that counts the strings S for which the array X built by the algorithm above matches F at that position.

Input

The first line contains the number of rows N of F, the number of columns M of F, the number of columns W of X, and the row index $i_0$ and column index $j_0$ where the top left cell of F sits. ( $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$ )

Each of the next N lines contains one row of F, written as M lowercase letters.

Output

Print the number of strings S that satisfy the condition, modulo 1,000,000,009.

Examples3

Example 1
Input
```
2 3 7 1 1
dea
abc
```
Expected output
```
1
```
Example 2
Input
```
1 5 6 1 0
xyxxy
```
Expected output
```
28
```
Example 3
Input
```
3 6 6 0 0
gogogo
jijiji
rarara
```
Expected output
```
0
```