Maneuver Path Weight Summation

You are given an island represented as an m×n grid. Each cell of the grid contains a terrain character. A "maneuver path" is defined as a simple (non-self‐intersecting) path of at least two cells that follows 8‐connectivity (two cells are adjacent if they share a common vertex) and satisfies the following condition:

• Let s be the starting cell and t the ending cell of the path, where s and t are different. For every step from a current cell u to its neighbor v, the move must not go further away from t in both coordinates. In other words, if u=(x,y) and t=(p,q), then for the move to v=(x',y') it must hold that \[ |p - x'| \le |p - x| \quad \text{and} \quad |q - y'| \le |q - y|. \] Equivalently, if x ≠ p then when x<p the allowed increment in the x-coordinate is {0, +1} (and if x=p then only 0 is allowed), and if x>p the allowed increment is {0, -1}; similarly for the y-coordinate.

The terrain sequence of a maneuver path is defined as the concatenation of the terrain characters on the cells along the path (in order from s to t). For a given maneuver path, its weight is the total number of maneuver paths (including itself) that have exactly the same terrain sequence. Your task is to compute the sum of the weights over all maneuver paths on the island.

Note: Two paths are considered different if the sequences of grid cells they pass through differ, even if the resulting terrain sequence is identical. In the final answer each group of paths sharing the same terrain sequence contributes the square of its size to the overall sum.

Hint: If a group has k paths having an identical terrain sequence, their total contribution is k². Thus, if you let F(seq) be the frequency of appearance of terrain sequence seq among all maneuver paths, you must output:

[ \sum_{\text{seq}} F(seq)^2. ]

inputFormat

The first line contains two integers m and n (1 ≤ m, n ≤ 5) representing the dimensions of the grid. The next m lines each contain a string of length n representing the terrain of each row.

You can assume the grid is small so that an exhaustive search over all pairs of distinct cells s and t and all corresponding maneuver paths is feasible.

outputFormat

Output a single integer — the sum of the weights of all maneuver paths. (For every group of paths with the same terrain sequence, add the square of the group’s size.)

sample

2 2
ab
cd

20