Гиперактивная Девочка
Хелен — очень активная девочка. Она хочет составить расписание своих занятий так, чтобы в любой момент дня у неё было чем заняться. Её не беспокоит, если занятия пересекаются по времени, главное, чтобы на каждый момент дня было запланировано какое-то занятие.
Хелен разделила день особым образом. День начинается в момент времени 0 и заканчивается в момент времени M. Каждый момент дня представлен вещественным числом между 0 и M, включительно. Хелен составила список всех возможных занятий с указанием времени их начала и окончания. Теперь ей нужно решить, какое подмножество занятий включить в расписание.
Если занятие начинается в момент времени S и заканчивается в момент времени F, то считается, что оно охватывает все моменты между S и F, включительно. Хелен не хочет тратить занятия впустую, поэтому она выберет только минимальные подмножества занятий, которые покрывают весь день. Подмножество занятий является минимальным, если и только если:
каждый момент дня покрыт хотя бы одним занятием из подмножества; и
удаление любого из занятий из подмножества оставит хотя бы один момент дня непокрытым.
Заметьте, что некоторые моменты дня могут быть покрыты более чем одним занятием. Учитывая список возможных занятий на один день, вы должны помочь Хелен, определив, сколько различных минимальных подмножеств покрывают день.
Входные данные
Каждый тестовый случай задается с использованием нескольких строк. Первая строка содержит два целых числа M и N, представляющих соответственно максимальное значение для момента дня (1 ≤ M ≤ 10^9) и количество возможных занятий на день (1 ≤ N ≤ 100). Каждая из следующих N строк описывает одно возможное занятие и содержит два целых числа S и F, представляющих соответственно время начала и окончания занятия (0 ≤ S < F ≤ M).
Последний тестовый случай завершается строкой, содержащей два нуля.
Выходные данные
Для каждого тестового случая выведите одну строку с одним целым числом, представляющим количество минимальных подмножеств, которые покрывают день. Чтобы облегчить вам задачу, выведите остаток от деления решения на 10^8.