Гіперактивна дівчинка
Гелен — гіперактивна дівчина, яка прагне скласти розклад своїх занять так, щоб у будь-який момент дня у неї було хоча б одне заняття. Їй не важливо, якщо її заняття перетинаються в часі, головне, щоб кожен момент її дня був запланований.
Гелен поділила свій день особливим чином: він починається в момент часу 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.