Ami la pasta e ogni giorno cucini e mangi pasta per cena. Sai preparare $3$ tipi di pasta: al sugo di pomodoro, alla panna e al pesto di basilico.
Hai deciso di pianificare il programma delle cene per $N$ giorni. In ciascun giorno scegli $1$ tipo di pasta tra i $3$ disponibili. Tuttavia, poiché ti stancheresti di mangiare sempre la stessa pasta di seguito, non devi scegliere la stessa pasta per $3$ o più giorni consecutivi. Inoltre, la pasta per $K$ giorni sui $N$ giorni totali è già stata decisa.
Dati il valore di $N$ e le informazioni sulla pasta per $K$ giorni, scrivi un programma per calcolare il resto della divisione per $10000$ del numero di programmi che soddisfano le condizioni.
Input
L'input è composto da $K + 1$ righe.
La $1$-a riga contiene $2$ interi $N, K$ ($3 \le N \le 100$, $1 \le K \le N$) separati da uno spazio.
La $(1 + i)$-esima riga ($1 \le i \le K$) contiene $2$ interi $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$) separati da uno spazio. Ciò significa che la pasta del giorno $A_i$ è già stata decisa: quando $B_i = 1$ è al sugo di pomodoro, quando $B_i = 2$ è alla panna e quando $B_i = 3$ è al pesto di basilico. Tutti gli $A_i$ ($1 \le i \le K$) sono distinti. Nei dati di input forniti, è garantito che esista almeno $1$ programma che soddisfa le condizioni.
Output
Stampa su una singola riga il resto della divisione per $10000$ del numero di programmi che soddisfano le condizioni.
Esempi di input e output
Input di esempio 1
5 3 3 1 1 1 4 2
Output di esempio 1
6
Nell'esempio $1$, consideri un programma per $5$ giorni. Il giorno $1$ e il giorno $3$ sono al sugo di pomodoro, mentre il giorno $4$ è alla panna. Inoltre, non devi scegliere la stessa pasta per $3$ o più giorni consecutivi. Ci sono $6$ programmi che soddisfano queste condizioni.
| Giorno 1 | Giorno 2 | Giorno 3 | Giorno 4 | Giorno 5 | |
|---|---|---|---|---|---|
| Programma 1 | 1 | 2 | 1 | 2 | 1 |
| Programma 2 | 1 | 2 | 1 | 2 | 2 |
| Programma 3 | 1 | 2 | 1 | 2 | 3 |
| Programma 4 | 1 | 3 | 1 | 2 | 1 |
| Programma 5 | 1 | 3 | 1 | 2 | 2 |
| Programma 6 | 1 | 3 | 1 | 2 | 3 |
In questa tabella, $1$ rappresenta il sugo di pomodoro, $2$ rappresenta la panna e $3$ rappresenta il pesto di basilico.
Input di esempio 2
20 5 10 2 4 3 12 1 13 2 9 1
Output di esempio 2
2640
Nell'esempio $2$, ci sono in totale $4112640$ programmi che soddisfano le condizioni. Si stampa $2640$, che è il resto della divisione per $10000$.