Sonya and Matrix Beauty

1000ms

262144K

Description:

Sonya had a birthday recently. She was presented with the matrix of size $$$n\times m$$$ and consist of lowercase Latin letters. We assume that the rows are numbered by integers from $$$1$$$ to $$$n$$$ from bottom to top, and the columns are numbered from $$$1$$$ to $$$m$$$ from left to right.

Let's call a submatrix $$$(i_1, j_1, i_2, j_2)$$$ $$$(1\leq i_1\leq i_2\leq n; 1\leq j_1\leq j_2\leq m)$$$ elements $$$a_{ij}$$$ of this matrix, such that $$$i_1\leq i\leq i_2$$$ and $$$j_1\leq j\leq j_2$$$. Sonya states that a submatrix is beautiful if we can independently reorder the characters in each row (not in column) so that all rows and columns of this submatrix form palidroms.

Let's recall that a string is called palindrome if it reads the same from left to right and from right to left. For example, strings $$$abacaba, bcaacb, a$$$ are palindromes while strings $$$abca, acbba, ab$$$ are not.

Help Sonya to find the number of beautiful submatrixes. Submatrixes are different if there is an element that belongs to only one submatrix.

Input:

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1\leq n, m\leq 250)$$$ — the matrix dimensions.

Each of the next $$$n$$$ lines contains $$$m$$$ lowercase Latin letters.

Output:

Print one integer — the number of beautiful submatrixes.

Sample Input:

1 3
aba

Sample Output:

Sample Input:

2 3
aca
aac

Sample Output:

Sample Input:

3 5
accac
aaaba
cccaa

Sample Output:

Note:

In the first example, the following submatrixes are beautiful: $$$((1, 1), (1, 1)); ((1, 2), (1, 2));$$$ $$$((1, 3), (1, 3)); ((1, 1), (1, 3))$$$.

In the second example, all submatrixes that consist of one element and the following are beautiful: $$$((1, 1), (2, 1));$$$ $$$((1, 1), (1, 3)); ((2, 1), (2, 3)); ((1, 1), (2, 3)); ((2, 1), (2, 2))$$$.

Some of the beautiful submatrixes are: $$$((1, 1), (1, 5)); ((1, 2), (3, 4));$$$ $$$((1, 1), (3, 5))$$$.

The submatrix $$$((1, 1), (3, 5))$$$ is beautiful since it can be reordered as:


accca
aabaa
accca

In such a matrix every row and every column form palindromes.

Informação

Provedor Codeforces

Código CF1080E