[BJOI2017] 机动训练

> AM 4:45 > > 又是晴朗的好天气。 > > AM 5:00 > > 不要嘛，再睡一会 > > AM 5:05 > > 呜……欺负人

睡眼朦胧的菜酱 (?) 已经被二爷拉起来晨跑了。而这个时间你在做什么呢？ 咳咳，言归正传，最近菜酱的训练遇到了点小麻烦。 凌晨绕格瑞赛亚岛跑一圈是基本，在那之后，菜酱还要接受严格的机动训练。所谓机动训练，就是在紧急情况 (?) 下，高速且隐蔽地从位置 $s$ 移动到位置 $t$ 的训练。一般来说，$s$ 和 $t$ 是根据二爷的心情随机决定的，但是由于菜酱已经熟悉了地形，每次总是能找到不太费劲的路径，二爷决定增大难度。所谓增大难度，其实就是指定整条路径，这样菜酱就没办法抄近道了。当然，由于是为了实战而进行的训练，二爷也不会随便乱指定路径，至少不会故意绕路。然后发生的问题就是，如何才能「随机」一整条路径出来？二爷统计了全岛所有的合法路径，打算每次在这个表格里随机抽一条出来。但是很快二爷发现，许多路径所经过的地形是完全相同的，这类路径的训练会更加有用。于是二爷修改了随机策略，地形较为常见的路径权重会变得更大。 一次偶然的机会，菜酱看到了二爷的随机策略，并发动技能「过目不忘 (?)」记了下来。现在你要帮菜酱分析数据。 为什么是你？当然是因为否则就会被菜酱爆头 (并不)。 整个岛可以看作一片 $m\times n$ 的区域，每个格子有自己的地形。 一条路径由一系列八连通的格子组成，两个格子八连通当且仅当这两个格子拥有公共的顶点。 定义一条“机动路径”如下： 1. 它是一条不自交的路径，即路径上任意两个格子都不是同一个。 2. 它的起点和终点处于不同位置，换言之这条路径至少包含 $2$ 个格子。 3. 从起点开始，任何一步只能向不远离终点的方向移动，这里不远离指的是 $x$ 和 $y$ 两个方向都不远离。 举例说明： ```plain .....t ...... .---. -++... ---... .-s-. -s+... -s+..t .-+-. ---... ---... ..t.. ``` 图中加号和减号标明了与 $s$ 八连通的所有格子，其中加号是“不远离 $t$”的方向。 因此可以看出，如下路径是机动路径： ```plain ++++++t ......+t .......t +...... .....++. ......+. +...... ..++++.. ...+++.. s...... s++..... s+++.... ``` 而如下路径不是机动路径： ```plain \../---t .......t .s. |--..... ....../. /.. |....... s..../.. \.. s....... .\--/... .t. ``` 需要注意的是，某些不合法的路径甚至比机动路径还要短，这是因为机动路径不是按照长度来定义的。 接下来定义一条机动路径的地形，岛上的地形由一个矩阵给出，如： ```plain .**. *..* *..* .**. ``` 那么，一条机动路径的地形序列就是它所经过的地形排成一列，如： ```plain s-\. ...\ ...| ...t ``` 地形序列就是 `.****.`。 每条机动路径的权重就是与之拥有相同地形序列的机动路径数量之和，例如与这条路径拥有相同地形序列的路径有 ```plain ./-t t... ...s s-\. ./-s s... ...t t-\. /... |... ...| ...\ /... |... ...| ...\ |... \... .../ ...| |... \... .../ ...| s... .\-s t-/. ...t t... .\-t s-/. ...s ``` 共 $8$ 条，注意回文时正反算两条，以及自己也算一条。 所以这条机动路径的权重是 $8$，同时所有这 $8$ 条机动路径的权重都是 $8$。 现在你需要统计所有的机动路径权重之和。 如果对这种统计方式没有直观的感受，可以查看样例说明。

第一行两个整数 $m,n$，表示岛的大小。 接下来 $m$ 行，每行 $n$ 个字符，表示岛的地形。

仅一个数，表示所有机动路径的权重之和。 由于这个数可能很大，你只需要输出它对 $10^9+9$ 取模的结果。

2 2
.*
*.

72

2 3
.*.
*.*

418

4 4
abba
baab
baab
abba

44512

### 样例解释 1 用中括号括起来的一些数对表示一条机动路径，坐标先行后列： - 地形序列 `.*`：$[(1, 1), (1, 2)],\ [(1, 1), (2, 1)],\ [(2, 2), (2, 1)],\ [(2, 2), (1, 2)]$，共 $4$ 条，每条权重为 $4$，计 $16$。 - 地形序列 `*.`：$[(1, 2), (1, 1)],\ [(2, 1), (1, 1)],\ [(2, 1), (2, 2)],\ [(1, 2), (2, 2)]$，共 $4$ 条，每条权重为 $4$，计 $16$。 - 地形序列 `..`：$[(1, 1), (2, 2)],\ [(2, 2), (1, 1)]$，共 $2$ 条，每条权重为 $2$，计 $4$。 - 地形序列 `**`：$[(1, 2), (2, 1)],\ [(2, 1), (1, 2)]$，共 $2$ 条，每条权重为 $2$，计 $4$。 - 地形序列 `.*.`：$[(1, 1), (1, 2), (2, 2)],\ [(1, 1), (2, 1), (2, 2)],\ [(2, 2), (2, 1), (1, 1)],\ [(2, 2), (1, 2), (1, 1)]$，共 $4$ 条，每条权重为 $4$，计 $16$。 - 地形序列 `*.*`：$[(1, 2), (1, 1), (2, 1)],\ [(2, 1), (1, 1), (1, 2)],\ [(1, 2), (2, 2), (2, 1)],\ [(2, 1), (2, 2), (1, 2)]$，共 $4$ 条，每条权重为 $4$，计 $16$。 共计 $16+16+4+4+16+16=72$。 ### 样例解释 2 - 地形序列 `.*`：$7$ 条，每条权重为 $7$，计 $49$。 - 地形序列 `*.`：$7$ 条，每条权重为 $7$，计 $49$。 - 地形序列 `..`：$4$ 条，每条权重为 $4$，计 $16$。 - 地形序列 `**`：$4$ 条，每条权重为 $4$，计 $16$。 - 地形序列 `..*`：$2$ 条，每条权重为 $2$，计 $4$。 - 地形序列 `.*.`：$10$ 条，每条权重为 $10$，计 $100$。 - 地形序列 `.**`：$2$ 条，每条权重为 $2$，计 $4$。 - 地形序列 `*..`：$2$ 条，每条权重为 $2$，计 $4$。 - 地形序列 `*.*`：$10$ 条，每条权重为 $10$，计 $100$。 - 地形序列 `**.`：$2$ 条，每条权重为 $2$，计 $4$。 - 地形序列 `.*.*`：$6$ 条，每条权重为 $6$，计 $36$。 - 地形序列 `*.*.`：$6$ 条，每条权重为 $6$，计 $36$。 共计 $49+49+16+16+4+100+4+4+100+4+36+36=418$。 ### 数据范围 - 对于 $10\%$ 的数据，$m\times n \le 4$。 - 对于 $30\%$ 的数据，$m, n \le 5$。 - 对于 $60\%$ 的数据，$m, n \le 10$。 - 另有 $20\%$ 的数据，所有地形均相同。 - 对于 $100\%$ 的数据，$1 \le m, n \le 30$，字符集由大小写字母，数字和 `.` `*` 构成。