Sie lieben Pasta und kochen sich jeden Tag zum Abendessen Pasta. Sie können $3$ Sorten Pasta zubereiten: mit Tomatensoße, mit Sahnesoße und mit Basilikumsoße.
Sie haben beschlossen, Ihren Abendessensplan für $N$ Tage aufzustellen. An jedem Tag wählen Sie $1$ der $3$ Pastasorten. Da es Ihnen jedoch überdrüssig wird, wenn es immer dieselbe Pasta gibt, dürfen Sie nicht an $3$ oder mehr aufeinanderfolgenden Tagen dieselbe Pasta wählen. Außerdem steht die Pasta für $K$ der $N$ Tage bereits fest.
Schreiben Sie ein Programm, das anhand des Wertes von $N$ und der Informationen über die Pasta für $K$ Tage den Rest berechnet, der bei der Division der Anzahl der gültigen Pläne durch $10000$ entsteht.
Eingabe
Die Eingabe besteht aus $K + 1$ Zeilen.
In der $1$. Zeile stehen $2$ durch ein Leerzeichen getrennte ganze Zahlen $N, K$ ($3 \le N \le 100$, $1 \le K \le N$).
In der $(1 + i)$-ten Zeile ($1 \le i \le K$) stehen $2$ durch ein Leerzeichen getrennte ganze Zahlen $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$). Dies bedeutet, dass die Pasta am Tag $A_i$ bereits feststeht: für $B_i = 1$ ist es Tomatensoße, für $B_i = 2$ Sahnesoße und für $B_i = 3$ Basilikumsoße. Alle $A_i$ ($1 \le i \le K$) sind paarweise verschieden. In den gegebenen Eingabedaten ist garantiert, dass es mindestens $1$ Plan gibt, der die Bedingungen erfüllt.
Ausgabe
Geben Sie den Rest bei der Division der Anzahl der gültigen Pläne durch $10000$ in einer Zeile aus.
Ein- und Ausgabebeispiele
Eingabebeispiel 1
5 3 3 1 1 1 4 2
Ausgabebeispiel 1
6
In Beispiel $1$ betrachten Sie einen Plan für $5$ Tage. Am $1$. und $3$. Tag gibt es Tomatensoße und am $4$. Tag Sahnesoße. Außerdem darf nicht an $3$ oder mehr Tagen hintereinander dieselbe Pasta gewählt werden. Es gibt $6$ Pläne, die diese Bedingungen erfüllen.
| Tag 1 | Tag 2 | Tag 3 | Tag 4 | Tag 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 |
In dieser Tabelle steht $1$ für Tomatensoße, $2$ für Sahnesoße und $3$ für Basilikumsoße.
Eingabebeispiel 2
20 5 10 2 4 3 12 1 13 2 9 1
Ausgabebeispiel 2
2640
In Beispiel $2$ gibt es insgesamt $4112640$ Pläne, die die Bedingungen erfüllen. Ausgegeben wird $2640$, der Rest bei der Division durch $10000$.