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

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

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

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

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

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

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

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

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

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

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

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

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

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

Во многих языках программирования есть функции, которые отвечают за заполнение всего массива или некоторой его части определенным значением. В языке Pascal это функция fillchar(), в Java — Arrays.fill(), в C++ — memset(). В новом языке программирования J# появилась функция mark(), которая умеет работать только с массивами логического типа.

Функция mark, вызванная от двух параметров \(a\) и \(b\), присваивает всем элементам массива с индексами от \(a\) до \(b\) включительно значение true, Так, если взять массив длины \(4\), элементы которого нумеруются с единицы и все значения в котором изначально равны false, и выполнить с ним операции mark(1, 3) и mark(2, 4), то весь массив окажется заполнен значениями true.

Одним из первых заданий для тех, кто начинает изучать J#, является написание программы, содержащей ровно \(M\) операций mark, и полностью заполняющей значениями true массив длины \(N\), изначально заполненный значениями false.

Вы быстро справились с этим заданием, и теперь задумались: сколькими различными способами это можно сделать? Различными считаются такие способы, в которых \(i\)-я операция mark в двух программах запущена с разными параметрами хотя бы для одного \(i\) от \(1\) до \(M\). Это число может быть большим, поэтому требуется посчитать его по модулю \(10^9 + 7\).