SPOJ Brasil

Helen é uma garota hiperativa. Ela quer agendar suas atividades de forma que em qualquer momento do dia haja ao menos uma atividade que ela possa fazer. Ela não se importa se suas atividades se sobrepõem no tempo, desde que cada momento do seu dia tenha uma atividade agendada.

Helen dividiu o dia de uma forma particular. O dia começa no tempo 0 e termina no tempo M. Cada momento do dia é representado por um número real entre 0 e M, inclusive. Helen fez uma lista de todas as possíveis atividades, com seus tempos de início e fim. Agora ela precisa escolher qual subconjunto de atividades vai agendar.

Se uma atividade começa no instante S e termina no instante F, então dizemos que ela cobre todo o período entre S e F, inclusive. Helen não quer desperdiçar nenhuma atividade, portanto ela vai escolher apenas subconjuntos mínimos de atividades que cobrem o dia a ser agendado. Um subconjunto de atividades é um subconjunto mínimo que cobre o dia se e somente se:

1. cada instante do dia é coberto por ao menos uma atividade do subconjunto; e
2. remover qualquer uma das atividades do subconjunto deixaria ao menos um instante do dia descoberto.

Note que alguns instantes do dia podem ser cobertos por mais de uma atividade.

Dada a lista de possíveis atividades para um dia, você deve ajudar Helen determinando quantos subconjuntos mínimos distintos de atividades cobrem o dia inteiro.

Entrada

Cada caso de teste se estende por várias linhas. A primeira linha contém dois inteiros M e N, representando respectivamente o maior valor de tempo do dia (1 ≤ M ≤ 10⁹) e o número de possíveis atividades para o dia (1 ≤ N ≤ 100). Cada uma das próximas N linhas descreve uma possível atividade e contém dois inteiros S e F, representando respectivamente os tempos de início e fim da atividade (0 ≤ S < F ≤ M).

O último caso de teste é seguido de uma linha contendo dois zeros.

Saída

Para cada caso de teste, imprima uma única linha com um único inteiro representando a quantidade de subconjuntos que cobrem o dia. Para tornar sua vida mais fácil, imprima apenas o resto ao dividir a solução por 10⁸.

Exemplo

Entrada:
8 7
0 3
2 5
5 8
1 3
3 6
4 6
0 2
1 1
0 1
2 1
0 1
0 0

Saída:
4
1
0