Problema A - Pirâmides

As pirâmides do Egipto são túmulos. Os faraós que as mandaram construir e os arquitectos que as desenharam, não as preparam para que os turistas do século XXI se divertissem subindo-as. No entanto, há sempre alguns visitantes mais ousados que ultrapassam as barreiras de segurança e se aventuram a trepar as pirâmides, para chegar lá acima e acenar estupidamente a bandeira do seu país.

Trepar as pirâmides é difícil e perigoso. Cada pirâmide é formada por camadas de pedras. Admitamos que a camada inferior, tem, em cada face, N pedras. A segunda camada, em cima dessa, terá N-1 pedras, cada uma apoiada sobre duas pedras inferiores. Assim, haverá N camadas. Para trepar a pirâmide, cada um destes "alpinistas" de algibeira, começa por subir uma das pedras da base; depois, passa dessa para uma das duas pedras da segunda camada que se apoiam sobre a pedra que ele trepou inicialmente; e assim sucessivamente, até chegar ao topo. Se a pirâmide estivesse em bom estado, com todas a pedras no lugar, haveria 2^N-1 "maneiras" diferentes de subir até ao topo, cada maneira correspondendo a um percurso pela pirâmide acima. No entanto, as pirâmides estão bastante degradadas e algumas pedras faltam ou estão tão deterioradas que se torna impossível subir para cima delas, para daí continuar a escalada. Fica assim a questão: nestas condições, quantas maneiras diferentes haverá de trepar a pirâmide até ao topo?

O Problema

Escreva um programa que dada uma pirâmide com N camadas, e uma descrição das pedras em falta ou muito deterioradas numa das faces da pirâmide, calcule o número de maneiras diferentes de subir a pirâmide até ao topo, começando por uma qualquer das pedras da primeira camada, evitando as pedras que estão em falta ou muito deterioradas.

Input

Na primeira linha vem o número N que representa o número de pedras na primeira camada e também o número de níveis da pirâmide (1 ≤ N ≤ 1000). Na segunda linha vem o número D de pedras em falta ou muito deterioradas ( 0 ≤ D ≤ N * (N + 1) / 2). Nas D linhas seguintes vêm dois números, C e P, que descrevem cada uma destas pedras em falta ou muito deterioradas: C representa a camada (1 ≤ C ≤ N), e P representa a posição da pedra nessa camada (1 <= P <= N - (C - 1)).

Output

Uma única linha, na qual existe um único número: o número de maneiras diferente de subir a pirâmide. É garantido que nos casos de teste este número será inferior a 2⁶³.

Exemplo de Input 1

4
2
2 1
3 2

Exemplo de Output 1

2

Exemplo de Input 2

5
3
3 2
2 3
1 4

Exemplo de Output 2

5