Rakastat pastaa ja valmistat sitä joka päivä päivälliseksi. Osaat valmistaa $3$ erilaista pastaa: tomaattikastikkeella, kermakastikkeella ja basilikakastikkeella.

Olet päättänyt suunnitella päivällisohjelmasi $N$ päiväksi. Jokaisena päivänä valitset $1$ lajin näistä $3$ pastalajista. Koska kyllästyisit samaan pastaan, jos söisit sitä jatkuvasti, et saa valita samaa pastaa $3$ tai useampana peräkkäisenä päivänä. Lisäksi $N$ päivän joukosta $K$ päivän pastat on jo päätetty etukäteen.

Kun syötteenä annetaan luku $N$ sekä tiedot $K$ päivän pastoista, kirjoita ohjelma, joka laskee ehdot täyttävien suunnitelmien lukumäärän jakojäännöksen luvulla $10000$ jaettuna.

Syöte

Syöte koostuu $K + 1$ rivistä.

Rivillä $1$ on välilyönnillä erotettuna $2$ kokonaislukua $N, K$ ($3 \le N \le 100$, $1 \le K \le N$).

Rivillä $(1 + i)$ ($1 \le i \le K$) on välilyönnillä erotettuna $2$ kokonaislukua $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$). Tämä tarkoittaa, että päivän $A_i$ pasta on jo päätetty: kun $B_i = 1$, se on tomaattikastike, kun $B_i = 2$, se on kermakastike, ja kun $B_i = 3$, se on basilikakastike. Kaikki $A_i$ ($1 \le i \le K$) ovat keskenään erisuuria. Annetussa syötteessä on taattu, että ehdot täyttäviä suunnitelmia on vähintään $1$.

Tuloste

Tulosta yhdelle riville jakojäännös, joka saadaan, kun ehdot täyttävien suunnitelmien lukumäärä jaetaan luvulla $10000$.

Syöte- ja tulosteesimerkit

Esimerkkisyöte 1

5 3
3 1
1 1
4 2

Esimerkkituloste 1

6

Esimerkissä $1$ mietit $5$ päivän suunnitelmaa. Päivinä $1$ ja $3$ on tomaattikastike ja päivänä $4$ kermakastike. Lisäksi samaa pastaa ei saa valita $3$ tai useampana päivänä peräkkäin. Näitä ehtoja vastaavia suunnitelmia on $6$ kappaletta.

Tässä taulukossa $1$ tarkoittaa tomaattikastiketta, $2$ kermakastiketta ja $3$ basilikakastiketta.

Esimerkkisyöte 2

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

Esimerkkituloste 2

2640

Esimerkissä $2$ ehdot täyttäviä suunnitelmia on yhteensä $4112640$ kappaletta. Tulostetaan $2640$, joka on jakojäännös jaettaessa luvulla $10000$.