Вы участвуете в испытаниях нового оружия. Для испытаний создан полигон, представляющий собой прямоугольное поле размера n × m, разделенное на единичные квадраты 1 × 1. На полигоне расположено k объектов, каждый из которых является прямоугольником со сторонами, параллельными сторонам полигона, занимающим полностью несколько единичных квадратов. Объекты не пересекаются и не касаются друг друга.
Принцип действия оружия сверхсекретен. Вам известно лишь то, что с помощью него можно нанести удар по любой прямоугольной области ненулевой площади со сторонами, параллельными сторонам полигона. Область должна накрывать полностью некоторые из единичных квадратов, на которые разбит полигон, и никак не затрагивать остальные квадраты. Разумеется, область не должна выходить за границы полигона. При этом вам поставлена задача: поразить не менее одного и не более трех прямоугольных объектов. Каждый объект должен лежать либо целиком внутри области (тогда он считается пораженным), либо целиком вне области.
Посчитайте количество способов нанести удар.