Du elsker pasta, og hver dag lager og spiser du pasta til middag. Du kan lage $3$ typer pasta: med tomatsaus, med fløtesaus og med basilikumsaus.

Du har bestemt deg for å legge en middagsplan for $N$ dager. Hver dag velger du $1$ type blant de $3$ typene pasta. Men siden du blir lei hvis du spiser samme pasta mange dager på rad, kan du ikke velge samme pasta $3$ eller flere dager på rad. I tillegg er pastaen for $K$ av de $N$ dagene allerede bestemt.

Gitt verdien av $N$ og informasjon om pastaen for $K$ dager, skriv et program som finner resten når antallet planer som oppfyller betingelsene, deles på $10000$.

Inndata

Inndata består av $K + 1$ linjer.

På linje $1$ står $2$ heltall $N, K$ ($3 \le N \le 100$, $1 \le K \le N$) atskilt med mellomrom.

På linje $(1 + i)$ ($1 \le i \le K$) står $2$ heltall $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$) atskilt med mellomrom. Dette betyr at pastaen på dag $A_i$ allerede er bestemt: når $B_i = 1$ er det tomatsaus, når $B_i = 2$ er det fløtesaus, og når $B_i = 3$ er det basilikumsaus. Alle $A_i$ ($1 \le i \le K$) er forskjellige. I de oppgitte inndataene er det garantert at det finnes minst $1$ plan som oppfyller betingelsene.

Utdata

Skriv på én enkelt linje ut resten når antallet planer som oppfyller betingelsene, deles på $10000$.

Eksempler på inndata og utdata

Eksempelinndata 1

5 3
3 1
1 1
4 2

Eksempelutdata 1

6

I eksempel $1$ ser du på en plan for $5$ dager. Dag $1$ og dag $3$ er tomatsaus, og dag $4$ er fløtesaus. Dessuten kan du ikke velge samme pasta $3$ eller flere dager på rad. Det er $6$ planer som oppfyller disse betingelsene.

I denne tabellen representerer $1$ tomatsaus, $2$ representerer fløtesaus, og $3$ representerer basilikumsaus.

Eksempelinndata 2

20 5
10 2
4 3
12 1
13 2
9 1

Eksempelutdata 2

2640

I eksempel $2$ er det totalt $4112640$ planer som oppfyller betingelsene. Vi skriver ut $2640$, som er resten når dette deles på $10000$.