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

Недавно образованное почтовое агентство «Экс-Федя» предлагает уникальную услугу — коллективную посылку. Эта услуга позволяет отправлять посылки жителям всех городов на каком-либо пути по цене обычной посылки. Удивительно, но пользоваться такой услугой стали только волшебники Флатландии, которые стали в большом количестве отправлять друг другу магические кактусы. Агентство столкнулось с непредвиденной проблемой: как известно, все волшебники живут в башнях и мало того, что не строят в них лестницы, так еще время от времени меняют их высоту. Поэтому, чтобы доставить посылку волшебнику, который живет в башне высотой h , курьеру агентства требуется иметь с собой не менее h метров веревки.

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

Рассмотрим следующую игру об удалении вершин из графа, представляющего лес (то есть объединение нескольких деревьев). Изначально граф состоит из одного дерева из n вершин, а количество очков равно 0 .

Игра задаётся перестановкой вершин и происходит следующим образом:

1. Если граф опустел, то игра заканчивается.
2. Иначе выбирается первая ещё не удалённая вершина в перестановке, после чего
3. Количество очков увеличивается на размер дерева из которого была выбрана вершина, а затем выбранная вершина и все связанные с ней рёбра удаляются, и тот же процесс продолжается на оставшемся графе.

Просуммируем число очков по всем возможным n ! играм. Выведите это число по модулю 10 ⁹ + 7 .

Ивица — страстный компьютерщик. Недавно он начал работать над своей первой компьютерной игрой — клоном популярного тетриса. Хотя игра далека от завершения, его программа уже поддерживает размещение в матрице N × M пяти разных фигур Тетриса (показанных на изображении ниже) в матрице. Перед тем, как поместить фигуру в матрицу, её можно поворачивать на 90 градусов произвольное число раз и можно окрашивать. Кроме того, текущая версия игры не поддерживает размещение фигуры, если она при этом выходит за границы матрицы или перекрывается с другими существующими фигурами в матрице.

Пока Ивица учился в школе, его сестра Марика начала игру и случайным образом повернула, покрасила и поместила фигуры, но таким образом, что соседние фигуры окрашены по-разному. Две фигуры смежны, если они имеют общую сторону или общий угол.

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

Мирко стал генеральным директором крупной корпорации. В компании работает N человек, пронумерованных от 1 до N , Мирко имеет номер 1 . У всех кроме Мирко есть начальник. Начальник может иметь несколько подчинённых, но не более одного своего начальника.

Когда Мирко получает задание от инвесторов, он передаёт его своему подчинённому с наименьшим номером. Этот подчинённый также передаёт его своему подчинённому с наименьшим номером, и так далее, пока задание не перейдёт несчастливому работнику без подчинённых, который должен сделать задание.

Этот работник получает 1 монету, его начальник получает 2 монеты, начальник этого начальника получает 3 и так далее. Потом тот, кто на самом деле сделал работу, осознаёт, насколько эта капиталистическая система несправедлива и увольняется с работы.

Мирко получает задания до тех пор, пока в корпорации не останется всего один сотрудник — сам Мирко. Тогда он выполняет это задание, получает 1 монету и уходит из корпорации. Ему стало интересно, сколько всего монет получил каждый бывший сотрудник. Помогите ему с этим.

Петя увлёкся алгоритмами сжатия данных. Он уже изучил форматы gz , bz , zip и несколько других. Воодушевившись новыми знаниями, Петя собрался разработать свой формат сжатия и назвать его dis .

Петя решил сжимать таблицы. У него есть таблица, состоящая из n строк и m столбцов, заполненная целыми положительными числами. Он хочет заменить значения элементов таблицы на целые положительные числа так, чтобы отношение элементов в каждой строке и каждом столбце не изменилось. То есть, если в некоторой строке исходной таблицы a _{i , j} < a _{i , k} , то и в сжатой таблице a ' _{i , j} < a ' _{i , k} , и если a _{i , j} = a _{i , k} , то a ' _{i , j} = a ' _{i , k} . Аналогично, если в некотором столбце исходной таблицы a _{i , j} < a _{p , j} , то и в сжатой таблице a ' _{i , j} < a ' _{p , j} , и если a _{i , j} = a _{p , j} , то a ' _{i , j} = a ' _{p , j} .

Поскольку б'{о}льшие значения требуют больше места для хранения, максимальное значение элемента получившейся матрицы должно быть как можно меньше.

В теории Петя мастер, но вот писать код он не любит. Помогите ему реализовать формат сжатия dis .