题目名称 #2178. 「BJOI2017」机动训练

时间限制：传统 2000 ms 内存限制：256 MiB 通过次数：123 提交次数：352

背景 菜酱被二爷拉起来晨跑，还要接受机动训练。 机动训练：在紧急情况下，高速隐蔽地从 $s$ 移动到 $t$。 原本菜酱可以自己选路径，二爷为了加大难度，改为随机抽取整条路径。

二爷统计了岛上所有合法路径，但发现很多路径地形序列相同，因此训练价值更大。 于是修改随机策略：地形序列出现次数多的路径权重更大。

菜酱看到了二爷的随机策略，你来帮她分析数据。

岛屿模型 岛是一个 $m \times n$ 的网格，每个格子有地形（一个字符）。

八连通：两个格子有公共顶点。 机动路径定义如下：

不自交：路径上任意两个格子不同。

长度至少为 $2$：起点 $s$ 和终点 $t$ 不同。

不远离终点的方向移动：每一步在 $x$ 和 $y$ 方向上都不远离 $t$。 “不远离”意味着：朝着 $t$ 的方向（或不偏离）移动。 例如，如果 $t$ 在右上方，那么每一步的移动方向只能是 右、上、右上 三种之一。

地形序列：路径经过的格子的地形字符按顺序组成的字符串。

权重：一条机动路径的权重 = 与它有相同地形序列的所有机动路径的数量（包括自己）。

任务：计算所有机动路径的权重之和，对 $1000000009$ 取模。

样例 1 输入

text 2 2 .* *. 输出

text 72 解释 用 $(r,c)$ 表示第 $r$ 行第 $c$ 列的格子（从 $1$ 开始）。

地形序列 .*：4 条，每条权重 $4$，贡献 $16$ 路径：$(1,1)\to(1,2)$，$(1,1)\to(2,1)$，$(2,2)\to(2,1)$，$(2,2)\to(1,2)$

地形序列 *.：4 条，每条权重 $4$，贡献 $16$

地形序列 ..：2 条，每条权重 $2$，贡献 $4$

地形序列 **：2 条，每条权重 $2$，贡献 $4$

地形序列 .*.：4 条，每条权重 $4$，贡献 $16$

地形序列 .：4 条，每条权重 $4$，贡献 $16$

总和 = $16 + 16 + 4 + 4 + 16 + 16 = 72$

样例 2 输入

text 2 3 .*. . 输出

text 418 具体分解见原题。

样例 3 输入

text 4 4 abba baab baab abba 输出

text 44512 数据范围 对于 $10$ 的数据：$m \times n \le 4$

对于 $30$ 的数据：$m, n \le 5$

对于 $60$ 的数据：$m, n \le 10$

另有 $20$ 的数据：所有地形均相同

对于 $100$ 的数据：$1 \le m, n \le 30$，字符集由大小写字母、数字、.、* 构成。

输出格式 一个整数，所有权重和 $\bmod 1000000009$。