--->
2 задач
<---
Знаменитый художник Вася только что закончил работу над своим новым шедевром и хочет знать, сколько он сможет получить за свой труд.
Картина представляет собой прямоугольник N на M сантиметров, разделенный на маленькие квадратики 1 на 1 сантиметр со сторонами, параллельными сторонам картины. Для достижения гармонии каждый из этих квадратиков Вася покрасил одним из 26 особых цветов, обозначаемых маленькими латинскими буквами.
Стоимость картины в точности равна количеству «симпатичных» частей в ней. Частью картины называется любой прямоугольник, который может быть вырезан из нее по границам квадратиков. Часть называется «симпатичной», если при выполнении симметрии относительно ее центра получается прямоугольник, раскрашенный также, как и исходная часть. Например, в картине, раскрашенной так:
abc
acb
симпатичными являются все части, состоящие из одного квадратика (их 6), а также части
bc и a
cb и a
Напишите программу, которая по информации о шедевре Васи определит его стоимость.
В первой строке содержатся два числа N и M (1 ≤ N, M ≤ 100). В следующих N строках идут строки, состоящие из M маленьких латинских символов. Символ в i-й строке j-м столбце определяет цвет соответствующего квадратика картины.
Выведите стоимость шедевра — количество частей, симметричных относительно своего центра.
Комментарии к примерам тестов
Этот пример разобран в условии
Симпатичными являются шесть частей 1x1, одна часть 1x2 и сама картина.
Частичные ограничения
Первая группа состоит из тестов, в которых N, M ≤ 15. Данная группа оценивается в 30 баллов.
Вторая группа состоит из тестов, в которых N, M ≤ 50. Данная группа оценивается в 30 баллов.
2 3 abc acb
8
3 2 ab cc ba
8
Строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки abba, ata являются палиндромами.
Дана строчка. Ее подстрокой называется некоторая непустая последовательность подряд идущих символов. Напишите программу, которая определит, сколько подстрок данной строки является палиндромами.
Вводится одна строка, состоящая из маленьких латинских букв. Длина строки не превышает 100000 символов.
Выведите одно число — количество подстрок данной строки, являющихся палиндромами
aaa
6
aba
4