Anda sangat menyukai pasta, dan setiap hari Anda memasak serta memakan pasta untuk makan malam. Anda dapat membuat $3$ jenis pasta: saus tomat, saus krim, dan saus basil.
Anda memutuskan untuk menyusun jadwal makan malam selama $N$ hari. Pada setiap harinya, Anda memilih $1$ jenis dari $3$ jenis pasta tersebut. Namun, karena Anda akan bosan jika memakan pasta yang sama terus-menerus, Anda tidak boleh memilih pasta yang sama selama $3$ hari atau lebih berturut-turut. Selain itu, pasta untuk $K$ hari dari $N$ hari tersebut sudah ditentukan sebelumnya.
Diberikan nilai $N$ dan informasi pasta untuk $K$ hari sebagai masukan, buatlah program untuk mencari sisa pembagian banyaknya jadwal yang memenuhi syarat dengan $10000$.
Masukan
Masukan terdiri dari $K + 1$ baris.
Baris ke-$1$ berisi $2$ bilangan bulat $N, K$ ($3 \le N \le 100$, $1 \le K \le N$) yang dipisahkan oleh spasi.
Baris ke-$(1 + i)$ ($1 \le i \le K$) berisi $2$ bilangan bulat $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$) yang dipisahkan oleh spasi. Ini berarti bahwa pasta untuk hari ke-$A_i$ sudah ditentukan: jika $B_i = 1$ maka saus tomat, jika $B_i = 2$ maka saus krim, dan jika $B_i = 3$ maka saus basil. Semua $A_i$ ($1 \le i \le K$) berbeda satu sama lain. Pada data masukan yang diberikan, dijamin terdapat setidaknya $1$ jadwal yang memenuhi syarat.
Keluaran
Keluarkan sisa pembagian banyaknya jadwal yang memenuhi syarat dengan $10000$ dalam satu baris.
Contoh Masukan dan Keluaran
Contoh Masukan 1
5 3 3 1 1 1 4 2
Contoh Keluaran 1
6
Pada Contoh $1$, Anda menyusun jadwal untuk $5$ hari. Hari ke-$1$ dan hari ke-$3$ adalah saus tomat, dan hari ke-$4$ adalah saus krim. Selain itu, Anda tidak boleh memilih pasta yang sama selama $3$ hari atau lebih berturut-turut. Terdapat $6$ jadwal yang memenuhi syarat-syarat ini.
| Hari 1 | Hari 2 | Hari 3 | Hari 4 | Hari 5 | |
|---|---|---|---|---|---|
| Jadwal 1 | 1 | 2 | 1 | 2 | 1 |
| Jadwal 2 | 1 | 2 | 1 | 2 | 2 |
| Jadwal 3 | 1 | 2 | 1 | 2 | 3 |
| Jadwal 4 | 1 | 3 | 1 | 2 | 1 |
| Jadwal 5 | 1 | 3 | 1 | 2 | 2 |
| Jadwal 6 | 1 | 3 | 1 | 2 | 3 |
Pada tabel ini, $1$ menyatakan saus tomat, $2$ menyatakan saus krim, dan $3$ menyatakan saus basil.
Contoh Masukan 2
20 5 10 2 4 3 12 1 13 2 9 1
Contoh Keluaran 2
2640
Pada Contoh $2$, terdapat total $4112640$ jadwal yang memenuhi syarat. Keluarkan $2640$, yang merupakan sisa pembagiannya dengan $10000$.