Вася недавно начал изучать английский язык. Сейчас ему нужно выучить, как пишутся буквы латинского алфавита. Поскольку он еще не до конца запомнил некоторые из них, он решил немного потренироваться.
Он нашел клетчатый лист бумаги и начал писать на нем произвольные буквы латинского алфавита. В конце концов Вася написал n строк по m символов в каждой. Таким образом, он получил прямоугольную таблицу размера n × m, в каждой клетке которой была написана некоторая буква латинского алфавита. Пронумеруем строки этой таблицы сверху вниз целыми числами от 1 до n, а столбцы слева направо целыми числами от 1 до m.
После этого, взглянув на полученную прямоугольную таблицу, Вася заинтересовался следующим вопросом: сколько существует подтаблиц, для которых выполняются следующие два условия:
- в подтаблице содержится не более k клеток с символом «a»;
- символы, находящиеся во всех четырех угловых клетках подтаблицы, совпадают.
Формально, подтаблица определяется следующим образом. Она задается четырьмя целыми числами x1, y1, x2, y2 такими, что 1 ≤ x1 < x2 ≤ n, 1 ≤ y1 < y2 ≤ m. Тогда в подтаблице содержатся все такие клетки (x, y) (x — номер строки, y — номер столбца), для которых выполняются неравенства x1 ≤ x ≤ x2, y1 ≤ y ≤ y2. Угловыми клетками таблицы считаются клетки (x1, y1), (x1, y2), (x2, y1), (x2, y2).
Вася уже слишком устал, выписывая буквы на лист бумаги. Поэтому он просит Вас посчитать интересующую его величину.
Примечание
В первом примере имеется две искомые подтаблицы: первая имеет верхний левый угол в клетке (2, 2) и правый нижний угол в клетке (3, 3), вторая имеет верхний левый угол в клетке (2, 1) и правый нижний угол в клетке (3, 4).