D. Автобусы
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
265 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Мальчик Геральд учится в школе, и она находится довольно далеко от его дома. Поэтому ему приходится ежедневно ездить туда на автобусах. Путь от дома до школы представляет собой отрезок прямой, на котором расположено ровно n + 1 остановок. Все они пронумерованы целыми числами от 0 до n в порядке их следования начиная от дома Геральда. Остановка у дома имеет номер 0, а остановка у школы — номер n.

Между домом и школой ездят m автобусов: i-ый автобус ездит от остановки si до остановки ti (si < ti), проезжая через все промежуточные остановки в порядке их следования. При этом Геральд не дурак, и не будет выходить из автобуса, пока на нем еще можно ехать в сторону школы — очевидно, что это не имеет смысла. То есть Геральд может сесть на i-ый автобус на любой остановке с номером от si до ti - 1 включительно, а выйти из i-го автобуса он может только на остановке ti.

Геральд не может идти между остановками пешком, а также не может перемещаться в сторону от школы к дому.

Геральд хочет узнать, сколько у него способов доехать от дома до школы. Сообщите ему это число. Два способа считаются различными, если какой-то участок между остановками Геральд едет на разных автобусах. Поскольку число способов может быть слишком большим, сообщите остаток этого числа от деления на 1000000007 (109 + 7).

Входные данные

В первой строке даны два целых числа через пробел: n и m (1 ≤ n ≤ 109, 0 ≤ m ≤ 105). Далее следует m строк по два целых числа si, ti в каждой — номера стартовых и конечных остановок автобусов (0 ≤ si < ti ≤ n).

Выходные данные

Выведите единственное число — количество способов доехать до школы по модулю 1000000007 (109 + 7).

Примеры
Входные данные
2 2
0 1
1 2
Выходные данные
1
Входные данные
3 2
0 1
1 2
Выходные данные
0
Входные данные
5 5
0 1
0 2
0 3
0 4
0 5
Выходные данные
16
Примечание

В первом тесте есть единственный вариант доехать до школы: сначала на первом автобусе до первой остановки, а потом на втором автобусе до второй остановки.

Во втором тесте никакой автобус не идет до третьей остановки, на которой расположена школа, поэтому правильный ответ — 0.

В третьем тесте Геральд может воспользоваться или не воспользоваться каждым из первых четырех автобусов, чтобы подъехать поближе к школе. Поэтому правильный ответ 24 = 16.