Ивану с детства нравились газеты. У него даже была мечта стать главным редактором газеты. Однажды ему представился шанс осуществить свою мечту. Чтобы устроиться на работу в издательство, ему необходимо выполнить тестовое задание — сверстать рекламное объявление.

Задано поле шириной \(W\) и высотой \(H\). Объявление должно состоять из одной или нескольких строк, в которых необходимо разместить в заданном порядке \(N\) слов. Про \(i\)-е слово известно, что при печати в стандартном масштабе оно занимает прямоугольник шириной \(a_i\) и высотой \(b_i.\)

Чтобы объявление выглядело красиво, все слова в нем должны быть напечатаны в одном масштабе. При печати в масштабе \(k\) размеры всех слов умножаются на \(k\). Если исходно слово занимало прямоугольник \(a_i \times b_i\) , то при печати в масштабе \(k\) оно занимает прямоугольник размером \((k \cdot a_i) \times (k \cdot b_i)\). Кроме того, если в строке более одного слова, то все слова в ней должны иметь одинаковую высоту. Разумеется, ни одно слово не должно выходить за границы поля.

На рисунке приведен пример красивого объявления с тремя словами.

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

Каждый день на его забор приклеивают новое объявление. Таким образом за последние \(n\) дней на забор наклеено уже \(n\) объявлений и Ивану кажется, что рекламой заклеен уже весь забор, состоящий из \(m\) досок. Доски пронумерованы вдоль забора от \(1\) до \(m\).

Оказалось, что в каждый из \(n\) дней когда приходил рекламный агент и приклеивал объявление, сосед Ивана Петр записывал, какие доски оказывались заклеены этим объявлением. А именно, выяснилось что в \(i\)-й день очередное объявление было наклеено таким образом, что занимало доски с \(l_i\)-й по \(r_i\)-ю включительно. При этом рекламный агент вполне мог заклеить новым объявлением полностью или частично свое же собственное объявление.

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

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

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

План мероприятия еще не готов, но известно, что план учений танков будет таким: танки должны будут проехать с одного острова на другой, пользуясь некоторыми мостами, причем не важно, какими именно мостами будут пользоваться танки. В Байтландии много мостов, которые были построены много лет назад и для танков совершенно не предназначены. Поэтому министр обороны решил укрепить некоторые мосты. А конкретно, он хочет укрепить несколько мостов так, чтобы вне зависимости от плана учений, выполнялось условие: если была возможность переехать с острова \(u\) на остров \(v\), то после укрепления некоторых мостов можно переехать с острова \(u\) на остров \(v\) по укрепленным мостам. При этом укрепление моста — дорогая операция, поэтому министр хочет укрепить минимальное число мостов.

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

Лягушонок Билли сидел на камне и любовался на закат, когда понял, что проголодался. Он огляделся и с удивлением обнаружил, что в ручье около него копошатся мошки. Ручей представляет собой прямую, на которой расположен и камень, на котором сидит Билли. Лягушонок был очень голоден, и потому захотел съесть всех мошек. У Билли очень длинный язык, поэтому он может, не спрыгивая с камня, съесть любую мошку (но только одну за раз).

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

Лягушонок Билли хочет понять — какое минимальное количество единиц энергии ему потребуется для того, чтобы съесть всех мошек. Помогите ему это выяснить.

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

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

Утром у Даниила было \(n\) яблок, а за день Даниил встретил \(k\) друзей. Выясните, сколько яблок у него могло остаться вечером.