В данной задаче речь пойдёт про упрощённую модель игры Pudding Monsters.

Важным этапом разработки любой игры является создание игровых карт. Поле для игры в Pudding Monsters представляет собой квадратную сетку n × n, в n клетках которой расположены монстры, а в некоторых остальных — игровые объекты. Игровая механика заключается в том, что игрок должен перемещать монстров по полю, при этом, оказавшись рядом, два маленьких монстра склеиваются в одного большого (они ведь из пудинга, вы же помните?).

Исследования показали, что самые интересные карты получаются, если исходно в каждой вертикали и каждой горизонтали расположено по монстру, а дальнейшая специфика карты уже задаётся правильной расстановкой остальных игровых объектов.

Частым приёмом для упрощения процесса разработки является переиспользование имеющихся ресурсов. Например, имея большую карту n × n, можно выделить из неё квадратную часть меньшего размера k × k, содержащую k монстров, и предложить в качестве упрощённой версии оригинальной карты.

Вас интересует, сколькими способами можно выделить из исходной карты квадратный фрагмент k × k (1 ≤ k ≤ n), содержащий ровно k монстров из пудинга. Определите это количество.