E. Соня и красота матрицы
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно у Сони был День рождения и ей подарили матрицу размером $$$n\times m$$$, элементы которой маленькие латинские буквы. Будем считать, что строки матрицы пронумерованы сверху вниз от $$$1$$$ до $$$n$$$, а столбцы слева направо от $$$1$$$ до $$$m$$$.

Подматрицей $$$(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)$$$ будем называть такие элементы $$$a_{ij}$$$ заданной матрицы, что $$$i_1\leq i\leq i_2$$$ и $$$j_1\leq j\leq j_2$$$. Соня считает подматрицу красивой, если мы можем независимо переупорядочить порядок символов в каждой строке (не в столбце) подматрицы так, чтобы все строки и столбцы подматрицы образовывали палиндромы.

Напомним, что строка называется палиндромом, если она одинаково читается как слева направо, так и справа налево. Например, строки $$$abacaba, bcaacb, a$$$ — палиндромы, а строки $$$abca, acbba, ab$$$ — нет.

Помогите Соне найти количество красивых подматриц данной матрицы. Подматрицы считаются разными, если существует элемент, что принадлежит только одной из двух подматриц.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ $$$(1\leq n, m\leq 250)$$$ — размеры матрицы.

Каждая из следующих $$$n$$$ строк содержит строку длины $$$m$$$ из латинских букв нижнего регистра.

Выходные данные

Выведите одно целое число — количество красивых подматриц данной матрицы.

Примеры
Входные данные
1 3
aba
Выходные данные
4
Входные данные
2 3
aca
aac
Выходные данные
11
Входные данные
3 5
accac
aaaba
cccaa
Выходные данные
43
Примечание

В первом примере подойдут следующие подматрицы: $$$((1, 1), (1, 1)); ((1, 2), (1, 2));$$$ $$$((1, 3), (1, 3)); ((1, 1), (1, 3))$$$.

Во втором примере подойдут все подматрицы состоящие из одного элемента, а также подматрицы: $$$((1, 1), (2, 1));$$$ $$$((1, 1), (1, 3)); ((2, 1), (2, 3)); ((1, 1), (2, 3)); ((2, 1), (2, 2))$$$.

Одними из вариантов в третьем примере могут быть подматрицы: $$$((1, 1), (1, 5)); ((1, 2), (3, 4));$$$ $$$((1, 1), (3, 5))$$$.

Подматрица $$$((1, 1), (3, 5))$$$ красивая, поскольку можно привести её к виду:


accca
aabaa
accca

Очевидно, что в такой матрице каждая строка и каждый столбец образовывают палиндромы.