eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Красиві прямокутники

Красиві прямокутники

В один прекрасний день першокласник Петрик прийшов додому, зробив уроки і почав думати, чим би йому зайнятись. Нічого цікавого в голову не приходило, тому Петрик взяв прямокутний клвтчатий аркуш паперу розміром \textbf{N} рядків на \textbf{M} стовбців і записав у кожній клітинці велику літеру англійського алфавіту. Англійську мову Петрик почав вивчати зовсім недавно, і тому поки він знає лише \textbf{5} перших літер алфавіту. Таким чином, у кожній клітинці аркушу виявилась записаною літера '\textbf{A}'..'\textbf{E}'. Подивившись на результати своєї праці, Петрик залишився незадоволеним - чи то аркуш виявився занадто великим, чи то літери на ньому були записані у поганому порядку. "\textit{Мабуть, ситуацію можна покращити, якщо вирізати з заданого аркуша прямокутник поменше,}" - подумав Петрик. "\textit{І, звичайно, вирізаний прямокутник повинен бути красивим!}" Але, що таке красивий прямокутник? Справа у тому, що Петрику не подобаються як прямокутники, у клітинках яких багато різних літер (\textbf{4} або \textbf{5}), так і прямокутники, у клітинках яких мало різних літер (\textbf{1} або \textbf{2}). Тому він вважає прямокутник красивим, якщо кількості різних літер у його клітинках рівно \textbf{3}-м. Допоможіть Петрику порахувати, сквлькома способами він може вирізати з заданого аркуша паперу красивий прямокутник. Розрізи можна робити лише по границям клітинок. Якщо заданий листок є красивим прямокутником, то, можливо, Петрик захоче нічого не вирізати і залишить заданий прямокутник повністю, і це також вважається одним зі способів вирізання. Зверніть увагу, що кожен спосіб вирізання можна однозначно задати четвіркою невід'ємних чисел (\textbf{a}, \textbf{b}, \textbf{c}, \textbf{d}), де \textbf{a} - кількість рядків, відрізаних від заданого аркуша зверху, \textbf{b} - кількість рядків, відрізаних знизу, \textbf{c} - кількість стовбців, відрізаних ліворуч, і \textbf{d} - кількість стовбців, відрізаних праворуч. Два способи вирізання, які задаються четвірками (\textbf{a}, \textbf{b}, \textbf{c}, \textbf{d}) і (\textbf{a'}, \textbf{b'}, \textbf{c'}, \textbf{d'}), вважаються різними, якщо виконується хоча б одна з нерівностей \textbf{a} ≠ \textbf{a'}, \textbf{b} ≠ \textbf{b'}, \textbf{c} ≠ \textbf{c'} або \textbf{d} ≠ \textbf{d'}. \InputFile У першому рядку задано кількість рядків \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{400}) написаних Петриком. Далі в \textbf{N} рядках задано сам масив рядків з вмістом заданого аркуша паперу. У рядку \textbf{t}\[\textbf{i}\] перераховуються зліва праворуч символи, записані у клітинках (\textbf{i+1})-ї зверху рядка аркуша. Кількість символів у рядку не перевищує \textbf{M} (\textbf{1} ≤ \textbf{M} ≤ \textbf{400}). \OutputFile Ціле число, рівне кількості способів вирізання красивого прямокутника із заданого аркуша паперу.
Ліміт часу 0.5 секунд
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
2
AAB
CCB
Вихідні дані #1
2
Автор Володимир Міняйлов