Ви дуже любите пасту і щодня готуєте та їсте її на вечерю. Ви вмієте готувати $3$ види пасти: з томатним соусом, із вершковим соусом та з базиліковим соусом.

Ви вирішили скласти розклад вечерь на $N$ днів. Кожного дня ви обираєте $1$ із $3$ видів пасти. Проте якщо їсти ту саму пасту поспіль, вона набридне, тому не можна обирати ту саму пасту $3$ або більше днів поспіль. Крім того, для $K$ днів із $N$ вид пасти вже визначено.

За заданим значенням $N$ та інформацією про пасту на $K$ днів напишіть програму, яка знайде остачу від ділення кількості розкладів, що задовольняють умови, на $10000$.

Вхідні дані

Вхідні дані складаються з $K + 1$ рядків.

У $1$-му рядку через пробіл записано $2$ цілі числа $N, K$ ($3 \le N \le 100$, $1 \le K \le N$).

У $(1 + i)$-му рядку ($1 \le i \le K$) через пробіл записано $2$ цілі числа $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$). Це означає, що пасту на $A_i$-й день уже визначено: коли $B_i = 1$ — це томатний соус, коли $B_i = 2$ — вершковий соус, а коли $B_i = 3$ — базиліковий соус. Усі $A_i$ ($1 \le i \le K$) різні. У наданих вхідних даних гарантується, що існує щонайменше $1$ розклад, який задовольняє умови.

Вихідні дані

Виведіть в одному рядку остачу від ділення кількості розкладів, що задовольняють умови, на $10000$.

Приклади вводу та виводу

Приклад вводу 1

5 3
3 1
1 1
4 2

Приклад виводу 1

6

У прикладі $1$ ви розглядаєте розклад на $5$ днів. У $1$-й і $3$-й дні — томатний соус, а в $4$-й день — вершковий соус. Також не можна обирати ту саму пасту $3$ або більше днів поспіль. Існує $6$ розкладів, які задовольняють ці умови.

У цій таблиці $1$ позначає томатний соус, $2$ — вершковий соус, а $3$ — базиліковий соус.

Приклад вводу 2

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

Приклад виводу 2

2640

У прикладі $2$ загалом існує $4112640$ розкладів, що задовольняють умови. Виводимо $2640$ — остачу від ділення на $10000$.