Du älskar pasta och lagar och äter pasta till middag varje dag. Du kan laga $3$ sorters pasta: med tomatsås, med gräddsås och med basilikasås.

Du har bestämt dig för att planera dina middagar för $N$ dagar. Varje dag väljer du $1$ sort bland de $3$ pastasorterna. Men eftersom du tröttnar om det blir samma pasta flera dagar i följd får du inte välja samma pasta $3$ eller fler dagar i rad. Dessutom är pastan för $K$ av de $N$ dagarna redan bestämd.

Givet värdet på $N$ samt information om pastan för $K$ dagar, skriv ett program som beräknar resten när antalet planer som uppfyller villkoren delas med $10000$.

Indata

Indata består av $K + 1$ rader.

På rad $1$ står $2$ heltal $N, K$ ($3 \le N \le 100$, $1 \le K \le N$) separerade med ett mellanslag.

På rad $(1 + i)$ ($1 \le i \le K$) står $2$ heltal $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$) separerade med ett mellanslag. Detta betyder att pastan för dag $A_i$ redan är bestämd: när $B_i = 1$ är det tomatsås, när $B_i = 2$ är det gräddsås och när $B_i = 3$ är det basilikasås. Alla $A_i$ ($1 \le i \le K$) är olika. I given indata garanteras att det finns minst $1$ plan som uppfyller villkoren.

Utdata

Skriv på en enda rad ut resten när antalet planer som uppfyller villkoren delas med $10000$.

Exempel på indata och utdata

Exempelindata 1

5 3
3 1
1 1
4 2

Exempelutdata 1

6

I exempel $1$ betraktar du en plan för $5$ dagar. Dag $1$ och dag $3$ är tomatsås, och dag $4$ är gräddsås. Dessutom får du inte välja samma pasta $3$ eller fler dagar i rad. Det finns $6$ planer som uppfyller dessa villkor.

I denna tabell står $1$ för tomatsås, $2$ för gräddsås och $3$ för basilikasås.

Exempelindata 2

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

Exempelutdata 2

2640

I exempel $2$ finns det totalt $4112640$ planer som uppfyller villkoren. Vi skriver ut $2640$, vilket är resten vid division med $10000$.