Vous adorez les pâtes et vous vous préparez des pâtes tous les jours pour le dîner. Vous savez cuisiner $3$ sortes de pâtes : sauce tomate, sauce à la crème et sauce au basilic.
Vous avez décidé de planifier vos menus du dîner pour $N$ jours. Chaque jour, vous choisissez $1$ sorte de pâtes parmi les $3$. Cependant, comme vous vous lasseriez de manger toujours les mêmes pâtes, vous ne devez pas choisir la même sorte de pâtes pendant $3$ jours consécutifs ou plus. De plus, les pâtes pour $K$ jours parmi les $N$ jours ont déjà été fixées.
Étant donné la valeur de $N$ et les informations sur les pâtes pour $K$ jours, écrivez un programme permettant de trouver le reste de la division par $10000$ du nombre de plannings qui respectent ces conditions.
Entrée
L'entrée se compose de $K + 1$ lignes.
La $1$-re ligne contient $2$ entiers $N, K$ ($3 \le N \le 100$, $1 \le K \le N$) séparés par un espace.
La $(1 + i)$-e ligne ($1 \le i \le K$) contient $2$ entiers $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$) séparés par un espace. Cela signifie que les pâtes du jour $A_i$ sont déjà fixées : lorsque $B_i = 1$, il s'agit de la sauce tomate ; lorsque $B_i = 2$, de la sauce à la crème ; et lorsque $B_i = 3$, de la sauce au basilic. Tous les $A_i$ ($1 \le i \le K$) sont distincts. Dans les données d'entrée fournies, il est garanti qu'il existe au moins $1$ planning respectant les conditions.
Sortie
Affichez sur une seule ligne le reste de la division par $10000$ du nombre de plannings respectant les conditions.
Exemples d'entrée et de sortie
Exemple d'entrée 1
5 3 3 1 1 1 4 2
Exemple de sortie 1
6
Dans l'exemple $1$, vous envisagez un planning sur $5$ jours. Les jours $1$ et $3$ sont à la sauce tomate, et le jour $4$ est à la sauce à la crème. De plus, vous ne devez pas choisir la même sorte de pâtes pendant $3$ jours consécutifs ou plus. Il y a $6$ plannings qui respectent ces conditions.
| Jour 1 | Jour 2 | Jour 3 | Jour 4 | Jour 5 | |
|---|---|---|---|---|---|
| Planning 1 | 1 | 2 | 1 | 2 | 1 |
| Planning 2 | 1 | 2 | 1 | 2 | 2 |
| Planning 3 | 1 | 2 | 1 | 2 | 3 |
| Planning 4 | 1 | 3 | 1 | 2 | 1 |
| Planning 5 | 1 | 3 | 1 | 2 | 2 |
| Planning 6 | 1 | 3 | 1 | 2 | 3 |
Dans ce tableau, $1$ représente la sauce tomate, $2$ la sauce à la crème et $3$ la sauce au basilic.
Exemple d'entrée 2
20 5 10 2 4 3 12 1 13 2 9 1
Exemple de sortie 2
2640
Dans l'exemple $2$, il y a au total $4112640$ plannings respectant les conditions. Affichez $2640$, qui est le reste de la division par $10000$.