Background

AM 4:45

Another clear and fine day.

AM 5:00

No way, just five more minutes...

AM 5:05

Waa... meanie...

Problem Description

Half-asleep, Cai Jiang (?) has been dragged out by Er Ye for a morning run. What about you at this time?

Anyway, let's get to the point. Recently, Cai Jiang's training has hit a snag.

Running around the island of Grasia at dawn is the norm, but after that, Cai Jiang has to undergo rigorous maneuver training. Maneuver training refers to the practice of moving quickly and covertly from position $s$ to position $t$ in emergency situations (?). Usually, $s$ and $t$ are determined randomly based on Er Ye's mood, but since Cai Jiang is familiar with the terrain, she always finds an easier path. Er Ye decided to increase the difficulty by specifying the entire path, so Cai Jiang can't take shortcuts. Of course, since the training is for practical purposes, Er Ye wouldn't randomly specify a path; at least not one that intentionally detours. The problem then becomes, how to "randomly" select an entire path? Er Ye has compiled a list of all valid paths on the island and plans to randomly pick one from this table each time. However, he soon realized that many paths pass through identical terrains, making these paths more useful for training. So, Er Ye modified the random strategy: paths with more common terrains would have higher weights.

By chance, Cai Jiang saw Er Ye's random strategy and activated her skill "photographic memory (?)" to memorize it. Now, you need to help Cai Jiang analyze the data.

Why you? Of course, because otherwise, you'd be in trouble (not really).

The entire island can be considered as an $m \times n$ region, with each grid having its own terrain.

A path consists of a series of 8-connected grids, where two grids are 8-connected if and only if they share a vertex.

Define a "maneuver path" as follows:

1. It is a non-self-intersecting path, meaning no two grids on the path are the same.
2. Its starting and ending points are different, implying the path must contain at least $2$ grids.
3. Starting from the beginning, each step can only move in a direction that does not move away from the endpoint, meaning neither the $x$ nor $y$ direction moves away.

For example:

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

The plus and minus signs mark all 8-connected grids with $s$, where the plus signs are directions that "do not move away from $t$".

Thus, the following paths are maneuver paths:

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

While the following paths are not maneuver paths:

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

Note that some invalid paths are even shorter than maneuver paths, as maneuver paths are not defined by length.

Next, define the terrain of a maneuver path. The island's terrain is given by a matrix, such as:

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

Then, the terrain sequence of a maneuver path is the sequence of terrains it passes through, such as:

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

The terrain sequence is .****..

The weight of each maneuver path is the sum of the number of maneuver paths that share the same terrain sequence. For example, the paths that share the same terrain sequence as this path are:

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

A total of $8$ paths, note that palindromes count as two, and the path itself counts as one.

So the weight of this maneuver path is $8$, and all $8$ of these maneuver paths have a weight of $8$.

Now, you need to calculate the sum of the weights of all maneuver paths.

If you don't have a直观感受 of this statistical method, you can refer to the sample explanation.

Input Format

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

The next $m$ lines, each containing $n$ characters, represent the terrain of the island.

Output Format

Output only one number, the sum of the weights of all maneuver paths.

Since this number may be very large, you only need to output the result modulo $10^9+9$.

Sample Input and Output

Input Sample #1

2 2
.*
*.

Output Sample #1

72

Input Sample #2

2 3
.*.
*.*

Output Sample #2

418

Input Sample #3

4 4
abba
baab
baab
abba

Output Sample #3

44512

Notes/Hints

Sample Explanation 1

Some pairs of numbers enclosed in brackets represent a maneuver path, with coordinates listed row first, then column:

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

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

Sample Explanation 2

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

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

Data Range

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

见题面 Input 部分

见题面 Output 部分