활동과잉 소년 강산이

활동을 좋아하는 강산이는 하루 중 단 한 순간이라도 쉬면 온몸에 가시가 돋아 고통을 받는다. 이렇게 24년을 살아온 강산이는 여러 개의 일을 동시에 진행할 수 있는 능력을 갖게 되었다.

하루는 시각 $0$에서 시작해 시각 $M$에서 끝나며, 하루의 모든 시각은 $0$ 이상 $M$ 이하의 실수로 나타낸다. 강산이는 오늘 할 수 있는 일들의 목록을 가지고 있고, 각 일에는 시작 시각 $S$와 끝 시각 $F$가 정해져 있다. 어떤 일을 고르면 시각 $S$부터 시각 $F$까지(양 끝점 포함) 빈틈없이 활동하게 된다.

강산이는 일을 되도록 아껴 두고 싶어서, 다음 두 조건을 모두 만족하는 최소 부분집합만 고르려 한다.

1. 하루의 모든 시각에서 적어도 하나의 일을 하고 있다. 즉, 고른 일들의 구간이 $[0, M]$ 전체를 덮는다.
2. 고른 일 중 어느 하나라도 빼면, 하루 중 아무 일도 하지 않는 시각이 반드시 생긴다. 즉, 어떤 일도 없어서는 안 된다.

최소 부분집합에서는 한 시각에 여러 일을 동시에 하고 있을 수도 있다.

오늘 할 수 있는 일들의 목록이 주어질 때, 서로 다른 최소 부분집합의 개수를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 하루의 끝 시각 $M$과 할 수 있는 일의 개수 $N$이 주어진다. ($1 \le M \le 10^9$, $1 \le N \le 100$)

이어지는 $N$개의 줄에는 각 일의 시작 시각 $S$와 끝 시각 $F$가 주어진다. ($0 \le S < F \le M$)

입력의 마지막에는 두 정수 $0$ $0$이 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 최소 부분집합의 개수를 $10^8$으로 나눈 나머지를 한 줄에 하나씩 출력한다.