Вася играет в очень интересную игру «Jumper». На специальной дорожке в ряд расположено несколько батутов. Батуты бывают двух типов: те, которые рассчитаны на прыжки в высоту, и те, которые рассчитаны на прыжки в длину. Игрок прыгает по батутам слева направо. При этом, первый свой прыжок он обязан сделать на любом батуте, который рассчитан на прыжок в длину (чтобы хорошенько разогнаться), после этого подпрыгнуть на батуте, который предназначен для прыжков в высоту (теперь он с разгона сможет подпрыгнуть очень высоко!). Игра ограничена по времени, поэтому игрок прыгает только на два батута.

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

Учительница по программированию задала Вовочке задачу — отсортировать массив из N различных чисел по возрастанию.

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

Но Вовочка — очень ленивый ученик. В какой-то момент ему надоело сортировать числа, и он решил посчитать, сколько ещё описанных выше обменов нужно сделать. Помогите ему.

От некоторых школ в командной олимпиаде по информатике участвует очень много команд. Учитель одной из таких школ раздал для регистрации своим командам номера: 1, 2, 3 и т. д. Для того чтобы проверить, все ли команды зарегистрировались, учитель выписал из таблицы регистрации только номера команд своей школы, но в том порядке, в котором команды регистрировались.

После нелёгких подсчётов оказалось, что зарегистрировались все. Но в процессе решения этой задачи учитель сформулировал следующую: сколькими способами можно выбрать стоящие подряд в этом списке K номеров команд, чтобы они образовывали некоторую перестановку чисел от 1 до K? Например, если от школы участвуют всего три команды, то при порядке регистрации 3 1 2 таких способов будет три (для K = 1, 2, 3), а при регистрации в порядке 2 3 1 — всего два (для K = 1 и K = 3).

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

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

Город N, в отличие от города M, расположен на склоне одного холма. Чистоту улиц этого города обеспечивает единственная поливальная машина. Бензин нынче дорог, поэтому движение муниципального транспорта «в гору» признано слишком расточительным.

Карта города представляет собой прямоугольник, разбитый на H × W клеток, где H и W — высота и ширина карты в клетках соответственно. Часть клеток заняты зданиями, остальные соответствуют улицам и площадям, которые и требуется помыть.

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

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

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