Hyperactive Boy Gangsan

Gangsan loves being active so much that if he rests for even a single instant during the day, thorns sprout all over his body and he suffers. Having lived like this for 24 years, he has gained the ability to work on any number of tasks at the same time.

A day starts at time $0$ and ends at time $M$, and every instant of the day is a real number between $0$ and $M$ inclusive. Gangsan has a list of tasks he can do today; each task has a start time $S$ and an end time $F$. If he picks a task, he is fully active from time $S$ to time $F$ inclusive (both endpoints included).

Gangsan wants to save his tasks, so he will only pick a minimal subset that satisfies both of the following conditions.

1. At every instant of the day he is doing at least one task. In other words, the chosen tasks' intervals cover the whole of $[0, M]$.
2. Removing any single one of the chosen tasks always creates an instant during the day at which he is doing nothing. In other words, no chosen task is redundant.

Within a minimal subset, several tasks may be running at the same instant.

Given the list of tasks Gangsan can do today, count the number of distinct minimal subsets.

The input consists of several test cases.

The first line of each test case contains the day's end time $M$ and the number of available tasks $N$. ($1 \le M \le 10^9$, $1 \le N \le 100$)

Each of the next $N$ lines contains a task's start time $S$ and end time $F$. ($0 \le S < F \le M$)

The input ends with a line containing two integers $0$ $0$, which must not be processed.

For each test case, print the number of minimal subsets modulo $10^8$, one per line.