Мирко стал генеральным директором крупной корпорации. В компании работает 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 .

Скажем, что последовательность строк t ₁ , ..., t _k является путешествием длины k , если для всех i > 1 t _i является подстрокой t _{i - 1} строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.

Определим путешествие по строке s как путешествие t ₁ , ..., t _k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u ₁ , ..., u _{k + 1} , такие, что s = u ₁ t ₁ u ₂ t ₂ ... u _k t _k u _{k + 1} . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.

Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .

Популярная сеть быстрого питания «McDuck's» открыла новый филиал в Берляндии. В ресторане установлено \(k\) плит. Для того чтобы приготовить бургер, надо жарить котлету в течение минуты на одной из плит, поэтому ресторан может готовить не более \(k\) бургеров в минуту.

Известно, что в «McDuck's» придут \(n\) клиентов. \(i\)-й из них придёт в момент времени \(t_i\), закажет \(x_i\) бургеров и будет готов заплатить за них \(c_i\) бурлей. Каждый клиент готов ждать заказ в течение \(w\) минут и, если через \(w\) минут после прихода он не получил \(x_i\) бургеров, он не заплатит ничего. При этом каждый клиент готов получать только свежие бургеры, то есть только те, котлеты для которых были поджарены не раньше времени \(t_i\). Из-за таких сложных требований ресторан не всегда сможет выполнить все заказы всех клиентов.

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

Назовем подпоследовательностью массива \(a\) непустой массив \(b\) такой, что он может быть получен из массива \(a\) удалением нескольких (возможно, никаких) элементов массива \(a\). Например, массив \([1, 3]\) является попоследовательностью массива \([1, 2, 3]\), но \([3, 1]\) не является.

Назовем подотрезком массива \(a\) непустой массив \(b\) такой, что он может быть получен путем удаления нескольких (возможно, никаких) первых и последних элементов массива \(a\). Например, \([1, 2]\) является подотрезком массива \([1, 2, 3]\), а \([1, 3]\) не является. Несложно заметить, что у массива длины \(n\) ровно \(\frac{n(n + 1)}{2}\) подотрезков.

Назовем массив \(a\) длины \(n\) возрастающим , если для любого \(1 \leq i < n\) выполняется \(a_i < a_{i + 1}\).

Монотонностью массива назовем количество его возрастающих подотрезков.

Дан массив \(a\) длины \(n\). Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю \(10^9 + 7\).