Вы очень любите пасту и каждый день готовите и едите ее на ужин. Вы умеете готовить $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$ подходящих расписаний. Выводим остаток от деления этого числа на $10000$, равный $2640$.