Þú elskar pasta og eldar og borðar pasta í kvöldmat á hverjum degi. Þú kannt að búa til $3$ tegundir af pasta: með tómatsósu, með rjómasósu og með basilíkusósu.

Þú hefur ákveðið að skipuleggja kvöldmatinn fyrir $N$ daga. Á hverjum degi velur þú $1$ tegund af þessum $3$ pastategundum. Hins vegar, þar sem þú færð leið á því að borða sama pastað ítrekað, máttu ekki velja sama pastað $3$ eða fleiri daga í röð. Auk þess hefur pastað fyrir $K$ daga af þessum $N$ dögum þegar verið ákveðið.

Miðað við gildið á $N$ og upplýsingar um pastað fyrir $K$ daga, skrifaðu forrit til að finna afganginn þegar fjöldi áætlana sem uppfylla skilyrðin er deilt með $10000$.

Inntak

Inntakið samanstendur af $K + 1$ línum.

Í $1$. línu eru $2$ heiltölur $N, K$ ($3 \le N \le 100$, $1 \le K \le N$) aðskildar með bili.

Í $(1 + i)$-tu línu ($1 \le i \le K$) eru $2$ heiltölur $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$) aðskildar með bili. Þetta þýðir að pastað á degi $A_i$ hefur þegar verið ákveðið: þegar $B_i = 1$ er það tómatsósa, þegar $B_i = 2$ er það rjómasósa og þegar $B_i = 3$ er það basilíkusósa. Öll $A_i$ ($1 \le i \le K$) eru ólík. Í gefnum inntaksgögnum er tryggt að til sé að minnsta kosti $1$ áætlun sem uppfyllir skilyrðin.

Úttak

Prentið í einni línu afganginn þegar fjöldi áætlana sem uppfylla skilyrðin er deilt með $10000$.

Dæmi um inntak og úttak

Inntaksdæmi 1

5 3
3 1
1 1
4 2

Úttaksdæmi 1

6

Í dæmi $1$ skoðar þú áætlun fyrir $5$ daga. Dagur $1$ og dagur $3$ eru með tómatsósu og dagur $4$ er með rjómasósu. Einnig má ekki velja sama pastað $3$ eða fleiri daga í röð. Það eru $6$ áætlanir sem uppfylla þessi skilyrði.

Í þessari töflu táknar $1$ tómatsósu, $2$ táknar rjómasósu og $3$ táknar basilíkusósu.

Inntaksdæmi 2

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

Úttaksdæmi 2

2640

Í dæmi $2$ eru alls $4112640$ áætlanir sem uppfylla skilyrðin. Prentað er $2640$, sem er afgangurinn þegar deilt er með $10000$.