활동과잉 소년 강산이

활동을 좋아하는 강산이는 하루 중 어떤 시간에라도 휴식을 했다가는 몸 전체에 가시가 돋아 고통을 받게 된다. 강산이는 이런 삶을 무려 24년간 살아왔고, 이에 따라 어떤 일이든, 몇 개의 일이든 동시에 진행할 수 있는 능력을 갖게 되었다.

강산이는 아침에 일어나면 우선 하루를 몇 개의 연속된 시각으로 나누어 하루 계획을 짠다. 하루는 시각 0에서 시작하며, 시각 M에 끝난다. 그리고 각 시각은 0부터 M 사이의 임의의 실수로 표현된다. 강산이는 그 날 할 수 있는 모든 일의 목록을 작성하고, 각각의 일이 시작될 시각과 끝날 시각 또한 기록한다. 이제 강산이는 할 수 있는 일의 어떤 부분집합을 고를 것이다.

만일 어떤 일이 시각 S에 시작해 F에 끝난다면, 시각 S부터 시각 F까지 완벽히 활동한 것이다.(양 끝점 또한 포함된다.)

강산이는 일을 많이 하고 싶지 않다. 물론 일을 하는 것이 힘든 것은 아니지만, 일을 최대한 아껴 두어야 다음 날에 그 일을 하면서 활동적인 하루를 보낼 수 있기 때문이다.

따라서 강산이는 일들의 부분집합 중 최소 부분집합을 하나 고를 것이다.

최소 부분집합은 아래와 같이 정의된다.

1. 하루 중 모든 시각에서, 강산이는 최소한 하나의 일은 하고 있다.
2. 부분집합에서 어떤 하나의 일을 제거할 경우, 항상 하루 중 강산이가 휴식을 취하는 시각이 존재하게 되어 버린다.

최소 부분집합에 의해 하루 중 어떤 시각은 여러 개의 일을 진행하고 있을 수도 있다.

이제 강산이가 오늘 할 수 있는 일들의 목록이 주어졌을 때, 최소 부분집합의 개수를 세어 보자.

각 테스트 케이스의 첫 줄에는 하루의 마지막 시각 M, 할 수 있는 일의 개수 N이 주어진다. (1 ≤ M ≤ 109, 1 ≤ N ≤ 100).

이어 N줄에 걸쳐, 각 일의 시작 시각 S와 끝나는 시각 F가 주어진다. (0 ≤ S < F ≤ M).

입력은 테스트 케이스의 첫 줄에 두 개의 정수 0 0이 주어질 때 끝난다.

각 테스트 케이스에 대해, 최소 부분집합의 개수를 108로 나눈 나머지를 출력한다.