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

В 2029 году три финала Всероссийской олимпиады — по химии, информатике и физкультуре — проводятся в Самаре. Из Саратова прошло много участников по каждому из этих предметов, и все они планируют ехать в Самару на поезде. Руководитель сборной по химии уже купил билеты для своих подопечных. Руководитель сборной по информатике как раз сейчас планирует этим заняться. Но программисты — странные люди, у которых есть много запросов к купленным местам. Например, они категорически не хотят ехать в одном вагоне со спортсменами (участниками сборной по физкультуре), а также со всеми другими людьми, не прошедшими на всерос (то есть, из всех возможных людей, они готовы терпеть только всероссников по химии).

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

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

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

Петя и Вова играют с надувными мячиками. Они стоят на расстоянии $$$L$$$ метров друг от друга. Каждую минуту Петя насосом надувает по одному мячику и бросает их в сторону Вовы, причём каждый мячик летит со скоростью $$$X$$$ метров в минуту. Если некоторый мячик оказывается на расстоянии меньшем или равном $$$D$$$ метров от Вовы, то Вова стреляет из пневматического пистолета в этот мячик, и тот лопается (выстрел происходит мгновенно, мячик лопается в тот же момент времени). Если же в какой-то момент есть несколько мячиков, находящихся на расстоянии меньшем или равном $$$D$$$ метров от Вовы, он стреляет в самый ближний к нему мячик. Мощности одного выстрела хватает только на то, чтобы лопнул один мячик. При этом, Вове требуется $$$M$$$ минут, чтобы повторно зарядить пневматический пистолет. Игра заканчивается тогда, когда до Вовы долетает мячик.

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

Для каждой подзадачи сообщаются набранные баллы, а также результат тестирования на всех тестах.

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

Мистер Барнум готов заплатить мистеру Карлайлу $$$x$$$ (история умалчивает чего), но тот ценит свой труд больше, и хочет получать $$$y$$$. Узнав об этом, мистер Барнум решил сторговаться и увеличил свое предложение на $$$a$$$. Мистер Карлайл пошел ему навстречу, и уменьшил свое предложение на $$$b$$$. После этого мистер Барнум поднял свое предложение на $$$2 \cdot a$$$, затем мистер Карлайл уменьшил свое предложение на $$$2 \cdot b$$$, затем мистер Барнум увеличил свое на $$$3 \cdot a$$$, и так далее...

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

Для каждой подзадачи сообщаются набранные баллы, а также результат тестирования на всех тестах.

Однажды Георгий пришел в военкомат и провел там весь день. Ему так там понравилось, что на следующий день он пришел туда еще раз!

Чтобы пройти процедуру, необходимо получить $$$k$$$ печатей. За каждой печатью нужно стоять в очереди, причем все печати нужно обязательно получать по порядку (то есть от $$$1$$$-й до $$$k$$$-й). Известно, что $$$i$$$-я печать ставится ровно $$$t_i$$$ времени.

В военкомат пришло $$$n$$$ человек, $$$i$$$-й пришел в момент времени $$$a_i$$$. Как только человек заходит в военкомат, он сразу встает в очередь за первой печатью (если два человека пришли в одно время, то первым встает человек с меньшим номером). Как только кому-то поставили печать, он мгновенно встает в очередь за следующей печатью (а на его место заходит следующий по очереди, если такой есть) или, если он получил $$$k$$$-ю печать, он уходит. Также, некоторые люди очень занятые, поэтому про $$$i$$$-го человека известно, что, если $$$b_i = 0$$$, то он готов ждать сколько угодно, а иначе, если он находится в военкомате хотя бы $$$b_i$$$ времени, то ему надоедает ждать, и он просто покидает военкомат, не закончив.

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

Георгий хороший математик, поэтому он смог посчитать сколько каждый человек провел времени в военкомате. А сможете ли вы?

У Арсения есть $$$n$$$ зверьков. Каждый из них обладает характером, поэтому, если в клетке, где находится $$$i$$$-й зверек, есть не больше $$$c_i$$$ зверьков, то его агрессивность будет $$$a_i$$$, а если больше, то его агрессивность будет $$$b_i$$$ ($$$a_i \le b_i$$$).

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

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

Для каждой подзадачи сообщаются набранные баллы, а также результат тестирования на всех тестах.

Саша и Артём поспорили на настольную игру, что Саша поедет следующим летом на стажировку в Google. Саша любит настольные игры, так что решительно намерена выиграть спор. Но для того, чтобы поехать стажироваться, нужно сначала пройти собеседование.

Саша выяснила, что на собеседовании соискателю предлагается решить одну задачу, от которой и зависит, проходишь ты или нет. Причём, данную задачу можно разбивать на подзадачи, а именно, если вам досталась задача с номером $$$\overline{a_1 \dots a_n}$$$, вы можете вместо неё решить задачи с номерами $$$\overline{a_1 \dots a_k}$$$ и $$$\overline{a_{k+1} \dots a_n}$$$ (например, вместо 571-й задачи можно решить задачи 5 и 71). Эти задачи, в свою очередь, тоже можно разбивать на подзадачи.

Саша считает задачу простой, если её номер является простым числом, и собирается, получив на собеседовании задачу, разбить её на простые подзадачи и решать их. Также девушка хочет, чтобы все эти подзадачи были небольшими, а именно, чтобы длина их номера не превышала $$$k$$$.

Саша получила задачу номер $$$n$$$, сколькими способами она может разбить её на нужные (небольшие и простые) подзадачи?

Так как число способов может быть большим, выведите его по модулю $$$10^9 + 7$$$.