The entire island can be viewed as an $n \times m$ area, where each cell has its own terrain. A path consists of a sequence of 8-connected cells. Two cells are 8-connected if and only if they share a common vertex.

A "maneuver path" is defined as follows: 1. It is a non-self-intersecting path, meaning no two cells on the path are the same. 2. Its start and end points are at different locations; in other words, the path contains at least 2 cells. 3. Starting from the start point, every step must move in a direction that does not move away from the end point. Here, "not moving away" means that neither the $x$ coordinate nor the $y$ coordinate moves away from the destination.

The terrain of a maneuver path is the sequence of terrains of the cells it passes through, arranged in order. The weight of each maneuver path is the sum of the number of maneuver paths that have the same terrain sequence. For example, if there are 8 paths with the same terrain sequence, the weight of each of these 8 paths is 8.

You need to calculate the sum of the weights of all maneuver paths.

Input

The input file is named makina.in. The first line contains two integers $n$ and $m$, representing the size of the island. The next $n$ lines each contain $m$ characters, representing the terrain of the island. The character set is provided in the constraints.

Output

The output file is named makina.out. Output a single integer representing the sum of the weights of all maneuver paths. Since this number can be very large, you only need to output the result modulo $1000000009$.

Examples

Input 1

2 2
.*
*.

Output 1

72

Note

The paths are represented by coordinate pairs (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, totaling 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, totaling 16. Terrain sequence "..": [(1, 1), (2, 2)], [(2, 2), (1, 1)], 2 paths in total, each with weight 2, totaling 4. Terrain sequence "*": [(1, 2), (2, 1)], [(2, 1), (1, 2)], 2 paths in total, each with weight 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)], 4 paths in total, each with weight 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)], 4 paths in total, each with weight 4, totaling 16. Total: 16+16+4+4+16+16=72.

Input 2

2 3
.*.
*.*

Output 2

418

Note

Terrain sequence ".": 7 paths, each with weight 7, totaling 49. Terrain sequence ".": 7 paths, each with weight 7, totaling 49. Terrain sequence "..": 4 paths, each with weight 4, totaling 16. Terrain sequence "": 4 paths, each with weight 4, totaling 16. Terrain sequence "..": 2 paths, each with weight 2, totaling 4. Terrain sequence "..": 10 paths, each with weight 10, totaling 100. Terrain sequence ".": 2 paths, each with weight 2, totaling 4. Terrain sequence "..": 2 paths, each with weight 2, totaling 4. Terrain sequence ".": 10 paths, each with weight 10, totaling 100. Terrain sequence "**.": 2 paths, each with weight 2, totaling 4. Terrain sequence "..": 6 paths, each with weight 6, totaling 36. Terrain sequence ".*.": 6 paths, each with weight 6, totaling 36. Total: 49+49+16+16+4+100+4+4+100+4+36+36=418.

Input 3

4 4
abba
baab
baab
abba

Output 3

44512

Note

The total sum of weights for all maneuver paths is 44512.

Constraints

For 10% of the data, $n \times m \le 4$. For 30% of the data, $n, m \le 5$. For 60% of the data, $n, m \le 10$. An additional 20% of the data has all terrain set to "6". For 100% of the data, $1 \le n, m \le 30$, and the character set consists of uppercase and lowercase letters, digits, ".", and "*".