Uwielbiasz makaron i codziennie na kolację gotujesz sobie makaron. Potrafisz przyrządzić $3$ rodzaje makaronu: z sosem pomidorowym, z sosem śmietanowym oraz z sosem bazyliowym.
Postanowiłeś zaplanować kolacje na $N$ dni. Każdego dnia wybierasz $1$ z $3$ rodzajów makaronu. Ponieważ jednak jedzenie wciąż tego samego makaronu szybko by Ci się znudziło, nie możesz wybrać tego samego makaronu przez $3$ lub więcej kolejnych dni. Ponadto dla $K$ spośród $N$ dni rodzaj makaronu został już ustalony.
Mając daną wartość $N$ oraz informacje o makaronie dla $K$ dni, napisz program, który wyznaczy resztę z dzielenia przez $10000$ liczby planów spełniających podane warunki.
Wejście
Wejście składa się z $K + 1$ wierszy.
W $1$. wierszu znajdują się $2$ liczby całkowite $N, K$ ($3 \le N \le 100$, $1 \le K \le N$) oddzielone spacją.
W $(1 + i)$-tym wierszu ($1 \le i \le K$) znajdują się $2$ liczby całkowite $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$) oddzielone spacją. Oznacza to, że makaron na dzień $A_i$ jest już ustalony: gdy $B_i = 1$, jest to sos pomidorowy, gdy $B_i = 2$, jest to sos śmietanowy, a gdy $B_i = 3$, jest to sos bazyliowy. Wszystkie wartości $A_i$ ($1 \le i \le K$) są parami różne. W podanych danych wejściowych gwarantuje się, że istnieje co najmniej $1$ plan spełniający warunki.
Wyjście
Wypisz w jednym wierszu resztę z dzielenia liczby planów spełniających warunki przez $10000$.
Przykłady wejścia i wyjścia
Przykład wejścia 1
5 3 3 1 1 1 4 2
Przykład wyjścia 1
6
W przykładzie $1$. rozważasz plan na $5$ dni. W dniach $1$. i $3$. jest sos pomidorowy, a w dniu $4$. sos śmietanowy. Ponadto nie można wybrać tego samego makaronu przez $3$ lub więcej dni z rzędu. Istnieje $6$ planów spełniających te warunki.
| Dzień 1 | Dzień 2 | Dzień 3 | Dzień 4 | Dzień 5 | |
|---|---|---|---|---|---|
| Plan 1 | 1 | 2 | 1 | 2 | 1 |
| Plan 2 | 1 | 2 | 1 | 2 | 2 |
| Plan 3 | 1 | 2 | 1 | 2 | 3 |
| Plan 4 | 1 | 3 | 1 | 2 | 1 |
| Plan 5 | 1 | 3 | 1 | 2 | 2 |
| Plan 6 | 1 | 3 | 1 | 2 | 3 |
W tej tabeli $1$ oznacza sos pomidorowy, $2$ oznacza sos śmietanowy, a $3$ oznacza sos bazyliowy.
Przykład wejścia 2
20 5 10 2 4 3 12 1 13 2 9 1
Przykład wyjścia 2
2640
W przykładzie $2$. istnieje łącznie $4112640$ planów spełniających warunki. Wypisujemy $2640$, czyli resztę z dzielenia tej liczby przez $10000$.