Мальчик Геральд учится в школе, и она находится довольно далеко от его дома. Поэтому ему приходится ежедневно ездить туда на автобусах. Путь от дома до школы представляет собой отрезок прямой, на котором расположено ровно n + 1 остановок. Все они пронумерованы целыми числами от 0 до n в порядке их следования начиная от дома Геральда. Остановка у дома имеет номер 0, а остановка у школы — номер n.
Между домом и школой ездят m автобусов: i-ый автобус ездит от остановки si до остановки ti (si < ti), проезжая через все промежуточные остановки в порядке их следования. При этом Геральд не дурак, и не будет выходить из автобуса, пока на нем еще можно ехать в сторону школы — очевидно, что это не имеет смысла. То есть Геральд может сесть на i-ый автобус на любой остановке с номером от si до ti - 1 включительно, а выйти из i-го автобуса он может только на остановке ti.
Геральд не может идти между остановками пешком, а также не может перемещаться в сторону от школы к дому.
Геральд хочет узнать, сколько у него способов доехать от дома до школы. Сообщите ему это число. Два способа считаются различными, если какой-то участок между остановками Геральд едет на разных автобусах. Поскольку число способов может быть слишком большим, сообщите остаток этого числа от деления на 1000000007 (109 + 7).
Примечание
В первом тесте есть единственный вариант доехать до школы: сначала на первом автобусе до первой остановки, а потом на втором автобусе до второй остановки.
Во втором тесте никакой автобус не идет до третьей остановки, на которой расположена школа, поэтому правильный ответ — 0.
В третьем тесте Геральд может воспользоваться или не воспользоваться каждым из первых четырех автобусов, чтобы подъехать поближе к школе. Поэтому правильный ответ 24 = 16.