字符生成板（CharacterBoard）

题目背景

Manao 有一块巨大得几乎看不到边界的字符板。他不会逐格填写字符，而是先写下一段较短的字符串作为“生成器”，再让生成器中的字符不断循环，按从左到右、从上到下的顺序铺满整块字符板。

后来，Manao 只在笔记中保留了字符板的一小块矩形区域。他希望知道：有多少个不同的生成器，能够产生一块与这段残片完全吻合的字符板？

题目描述

有一个字符矩阵 $X$，它有 $1\,000\,000\,000$ 行和 $W$ 列，行和列均从 $0$ 开始编号。

Manao 选择一个只包含小写英文字母的非空字符串 $S$ 作为生成器，并满足

随后按照行优先顺序，用 $S$ 的字符循环填充整个矩阵。等价的伪代码如下：

cur = 0
for i = 0 .. 999999999:
    for j = 0 .. W-1:
        X[i][j] = S[cur]
        cur = (cur + 1) mod |S|

现在给定一个 $N\times M$ 的字符矩阵 fragment，它是 $X$ 中左上角坐标为 $(i_0,j_0)$ 的连续子矩阵，即对于所有合法的 $i,j$，都有

请计算有多少个不同的生成器 $S$ 能够生成一个包含给定残片的矩阵 $X$。

两个生成器只要长度不同或任意一个位置的字符不同，就视为不同。

答案可能很大，请输出答案对 $1\,000\,000\,009$ 取模后的结果。

输入格式

第一行包含五个整数 $N,M,W,i_0,j_0$，分别表示残片的行数、列数，完整矩阵的列数，以及残片左上角在完整矩阵中的坐标。

接下来 $N$ 行，每行包含一个长度为 $M$、仅由小写英文字母组成的字符串，表示 fragment。

输出格式

输出一个整数，表示合法生成器的数量对 $1\,000\,000\,009$ 取模后的结果。

数据范围

• $1\le N\le 10$；
• $1\le M\le 10$；
• $M\le W\le 1\,000\,000\,000$；
• $0\le i_0\le 1\,000\,000\,000-N$；
• $0\le j_0\le W-M$；
• fragment 中只包含小写英文字母。

样例

样例 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

样例 4

3 10 8827 104 6022
abababacac
aaacacacbb
ccabababab

829146844

样例 5

4 8 20031 960124 1959
asjkffqw
basjkffq
qbasjkff
qqbasjkf

873850548

样例 6

10 10 1000000000 0 0
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa

471477008

样例说明

对于样例 1，唯一可行的生成器是 abcde。

对于样例 2，可行生成器包括 xyx、yxyxx，以及形如 xyxxy? 的字符串，其中 ? 可以是任意小写英文字母，因此答案为 $28$。

对于样例 3，不存在任何合法生成器。