Background

AM 4:45

Another clear, sunny day.

AM 5:00

Nooo, let me sleep a bit more.

AM 5:05

Ugh... bullying me.

Sleepy Caijiang (?) has already been dragged out by Er-ye for a morning run. And what are you doing at this time?

Ahem, back to the topic. Caijiang’s recent training has run into a small problem.

Running one lap around Grisaia Island before dawn is basic. After that, Caijiang must also undergo strict mobility training. “Mobility training” means, under an emergency situation (?), moving quickly and covertly from position $s$ to position $t$. In general, $s$ and $t$ are chosen at random according to Er-ye’s mood. But since Caijiang has already learned the terrain, she always finds a not-so-hard path, so Er-ye decided to increase the difficulty. Increasing the difficulty basically means specifying the entire path so that Caijiang cannot take shortcuts. Of course, because this is training for real combat, Er-ye will not assign paths arbitrarily, at least not deliberately detouring. The problem that arises is: how to “randomly” pick an entire path? Er-ye counted all legal paths on the whole island and planned to randomly draw one each time from this table. But he soon found that many paths go through exactly the same terrains, and such paths are more useful for training. So he changed the random strategy: paths with more common terrain sequences get larger weights.

By chance, Caijiang saw Er-ye’s random strategy and used the skill “photographic memory (?)” to memorize it. Now you need to help Caijiang analyze the data.

Why you? Because otherwise Caijiang will headshot you (not really).

The entire island can be seen as an $m\times n$ area, each cell with its own terrain.

A path is a sequence of 8-connected cells; two cells are 8-connected if and only if the two cells share a common corner.

Define a “mobility path” as follows:

1. It is a simple path, that is, no two cells on the path are the same.
2. Its start and end are in different positions; in other words, the path contains at least $2$ cells.
3. Starting from the beginning, each step can only move in a direction that does not move away from the destination; here “not moving away” means that in both the $x$ and $y$ directions you do not move away.

Illustration:

.....t    ......    .---.
-++...    ---...    .-s-.
-s+...    -s+..t    .-+-.
---...    ---...    ..t..

In the figure, plus and minus signs mark all cells that are 8-connected to $s$, where plus signs indicate directions that are “not moving away from $t$.”

Therefore, the following paths are mobility paths:

++++++t    ......+t    .......t
+......    .....++.    ......+.
+......    ..++++..    ...+++..
s......    s++.....    s+++....

And the following are not mobility paths:

\../---t    .......t    .s.
|--.....    ....../.    /..
|.......    s..../..    \..
s.......    .\--/...    .t.

Note that some illegal paths can even be shorter than mobility paths, because mobility paths are not defined by their length.

Next, define the terrain of a mobility path. The island’s terrain is given by a matrix, for example:

.**.
*..*
*..*
.**.

Then the terrain sequence of a mobility path is the terrains it passes through listed in order, such as:

s-\.
...\
...|
...t

The terrain sequence is .****..

The weight of each mobility path is the total number of mobility paths that have the same terrain sequence. For example, the paths that have the same terrain sequence as this path are

./-t    t...    ...s    s-\.    ./-s    s...    ...t    t-\.
/...    |...    ...|    ...\    /...    |...    ...|    ...\
|...    \...    .../    ...|    |...    \...    .../    ...|
s...    .\-s    t-/.    ...t    t...    .\-t    s-/.    ...s

There are $8$ of them. Note that when the sequence is a palindrome, forward and reverse still count as two, and the path itself also counts.

So the weight of this mobility path is $8$, and all these $8$ mobility paths have weight $8$ as well.

Now you need to sum the weights of all mobility paths.

If this counting method is not intuitive, see the sample explanations.

Problem Description

Input the island’s terrain grid and compute the sum of weights over all mobility paths, where the weight of a mobility path is the number of mobility paths sharing the same terrain sequence. Output the result modulo $10^9+9$.

Input Format

The first line contains two integers $m, n$, the size of the island.

Then follow $m$ lines, each containing $n$ characters, describing the island’s terrain.

Output Format

Output a single number, the sum of weights over all mobility paths, modulo $10^9+9$.

2 2
.*
*.

72

2 3
.*.
*.*

418

4 4
abba
baab
baab
abba

44512

Hint

Sample Explanation 1

Pairs in square brackets denote a mobility path, with coordinates in the order row, column:

• Terrain sequence .*: $[(1, 1), (1, 2)],\ [(1, 1), (2, 1)],\ [(2, 2), (2, 1)],\ [(2, 2), (1, 2)]$, $4$ paths in total, each with weight $4$, contributing $16$.
• Terrain sequence *.: $[(1, 2), (1, 1)],\ [(2, 1), (1, 1)],\ [(2, 1), (2, 2)],\ [(1, 2), (2, 2)]$, $4$ paths in total, each with weight $4$, contributing $16$.
• Terrain sequence ..: $[(1, 1), (2, 2)],\ [(2, 2), (1, 1)]$, $2$ paths in total, each with weight $2$, contributing $4$.
• Terrain sequence **: $[(1, 2), (2, 1)],\ [(2, 1), (1, 2)]$, $2$ paths in total, each with weight $2$, contributing $4$.
• Terrain sequence .*.: $[(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$ paths in total, each with weight $4$, contributing $16$.
• Terrain sequence *.*: $[(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$ paths in total, each with weight $4$, contributing $16$.

Total: $16+16+4+4+16+16=72$.

Sample Explanation 2

• Terrain sequence .*: $7$ paths, each with weight $7$, contributing $49$.
• Terrain sequence *.: $7$ paths, each with weight $7$, contributing $49$.
• Terrain sequence ..: $4$ paths, each with weight $4$, contributing $16$.
• Terrain sequence **: $4$ paths, each with weight $4$, contributing $16$.
• Terrain sequence ..*: $2$ paths, each with weight $2$, contributing $4$.
• Terrain sequence .*.: $10$ paths, each with weight $10$, contributing $100$.
• Terrain sequence .**: $2$ paths, each with weight $2$, contributing $4$.
• Terrain sequence *..: $2$ paths, each with weight $2$, contributing $4$.
• Terrain sequence *.*: $10$ paths, each with weight $10$, contributing $100$.
• Terrain sequence **.: $2$ paths, each with weight $2$, contributing $4$.
• Terrain sequence .*.*: $6$ paths, each with weight $6$, contributing $36$.
• Terrain sequence *.*.: $6$ paths, each with weight $6$, contributing $36$.

Total: $49+49+16+16+4+100+4+4+100+4+36+36=418$.

Constraints

• For $10\%$ of the testdata, $m\times n \le 4$.
• For $30\%$ of the testdata, $m, n \le 5$.
• For $60\%$ of the testdata, $m, n \le 10$.
• In an additional $20\%$ of the testdata, all terrains are the same.
• For $100\%$ of the testdata, $1 \le m, n \le 30$, and the character set consists of uppercase letters, lowercase letters, digits, and . *.

Translated by ChatGPT 5