Вася очень любит различные игры: шашки, шахматы, домино, крестики-нолики и т. д. Поскольку он играет в них уже достаточно давно, он успел изучить эти игры достаточно хорошо, и они стали скучными. Поэтому он теперь изобретает новые игры на основе тех, в которые уже наигрался. Недавно он изобрел игру «Доминошахматы».

Она состоит в следующем: Вася берет у дедушки большой кусок фанеры и раскрашивает его так, что у него получается шахматная доска размера N × M клеточек. Потом он берет кости домино и пытается покрыть ими полученную доску так, чтобы все клеточки были закрыты, не было наложений и никакие доминошки не торчали за края доски (каждая доминошка покрывает две соседние клетки).

Поскольку Вася не спрашивает разрешения у дедушки прежде, чем взять доску, он иногда берет ненужные доски, а иногда и те, которые дедушка хотел использовать в строительстве новой дачи. Как раз сегодня Вася взял «нужную» доску, поэтому дедушка был вынужден вырезать из Васиной доски два квадрата по одной клеточке.

Вася сначала огорчился, что не сможет поиграть в свою игру. А потом решил попробовать замостить доску с уже вырезанными клетками, причем так, чтобы вырезанные клетки не были накрыты доминошками.

Помогите Васе понять, можно ли это сделать.

Артур принимает участие в телешоу, в котором участникам необходимо выполнять различные интеллектуальные и физические задания, чтобы зарабатывать очки. В одном из таких заданий Артуру необходимо спасти маленького котенка.

Поле для выполнения задания представляет собой прямоугольник размером \(n \times m\) метров, разбитый на квадраты единичной площади. В одном из квадратов исходно находится Артур, в некотором другом квадрате находится котенок. Кроме того, один из квадратов содержит лифт, встав на который вместе с котенком, Артур успешно выполняет задание.

За один шаг Артур может перемещаться на любой квадрат, имеющий общую сторону с тем, на котором он стоит. После этого квадрат, на котором перед этим шагом стоял Артур, исчезает и больше на него вставать нельзя. Таким образом исчезают в том числе и квадрат, на котором исходно стоял Артур, и квадрат с котенком. Цель Артура - дойти до котенка, взять его и затем дойти до лифта. При этом очки за выполнение задания, зависят от числа шагов, которое сделает Артур, поэтому ему необходимо сделать минимальное число шагов.

Выяснив, сколько шагов ему придется сделать, Артур заинтересовался, сколько существует различных способов дойти до котенка, а затем с ним до лифта, сделав в сумме минимальное число шагов. Помогите ему это выяснить. Это число может быть довольно большим, поэтому Артур просит найти его по модулю \(10^9+7\).

Первокурсник Рома приехал в общежитие и, удивившись беспорядку в комнате и толстому слою пыли на полу, начал наводить порядок. Первым делом он решил вымыть пол. Для этого Рома в магазине приобрел инновационную швабру.

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

Рома живет в большой прямоугольной комнате. Рома провел сломанной шваброй от одной стороны комнаты до другой, не отрывая ее от стены, так что в результате отломанный угол швабры оказался в углу комнаты. При этом часть соответствующей прямоугольной полосы пола в углу осталась невымытой.

Рома считает, что все точки, в которых в какой-то момент находилась моющая часть швабры оказались вымыты. Теперь он решил выяснить, какая часть этой полосы осталась грязной.

Помогите ему вычислить площадь этой части. Можете считать, что размер комнаты, в которой живет Рома, существенно больше размеров моющей части швабры.

В одном уездном городе Эн было решено построить собственное метро. Все силы города были мобилизованы на выкапывание станций и прокладку подземных путей дедовскими лопатами.

Вся эта история нас бы совершенно не интересовала, если бы однажды в мэрию города не пришло письмо из далёкой страны Емакира. Оказалось, что компания Alpep подозревает администрацию уездного города в нарушении их патента на jMetro и грозится возбудить против города Эн дело. Согласно патенту, jMetro — это метро, в котором:

• существует ровно одна узловая станция, в которой начинаются все радиальные линии метро, и это единственная станция, принадлежащая хотя бы двум радиальным линиям;
• существует ровно одна кольцевая линия, все станции которой лежат на радиальных линиях, причём на каждой радиальной линии лежит ровно одна станция кольцевой линии;
• кольцевая линия не проходит через узловую станцию;
• кольцевая линия не проходит через конечные станции радиальных линий.

Поскольку компания Alpep известна своими необоснованными обвинениями в нарушениях патентов, мэрия города хочет проверить правомочность заявления компании.

В центре города Че есть пешеходная улица - одно из самых популярных мест для прогулок жителей города. По этой улице очень приятно гулять, ведь вдоль улицы расположено \(n\) забавных памятников.

Девочке Маше из города Че нравятся два мальчика из ее школы, и она никак не может сделать выбор между ними. Чтобы принять окончательное решение, она решила назначить обоим мальчикам свидание в одно и то же время. Маша хочет выбрать два памятника на пешеходной улице, около которых мальчики будут ее ждать. При этом она хочет выбрать такие памятники, чтобы мальчики не увидели друг друга. Маша знает, что из-за тумана мальчики увидят друг друга только в том случае, если они будут на расстоянии не более \(r\) метров.

Маше заинтересовалась, а сколько способов есть выбрать два различных памятника для организации свиданий.