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