Недавно у Сони был День рождения и ей подарили матрицу размером \(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\) — нет.
Помогите Соне найти количество красивых подматриц данной матрицы. Подматрицы считаются разными, если существует элемент, что принадлежит только одной из двух подматриц.
Примечание
В первом примере подойдут следующие подматрицы: \(((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
Очевидно, что в такой матрице каждая строка и каждый столбец образовывают палиндромы.