You love pasta and cook pasta for dinner every day. You can make $3$ kinds of pasta: tomato sauce, cream sauce, and basil sauce.

You have decided to plan your dinner schedule for $N$ days. On each day, you choose $1$ kind of pasta from the $3$ kinds. However, since you will get tired of eating the same pasta in a row, you must not choose the same pasta for $3$ or more consecutive days. Also, the pasta for $K$ days out of the $N$ days has already been decided.

Given the value of $N$ and the pasta information for $K$ days, write a program to find the number of schedules that satisfy the conditions, modulo $10000$.

Input

The input consists of $K + 1$ lines.

The $1$-st line contains $2$ integers $N, K$ ($3 \le N \le 100$, $1 \le K \le N$) separated by a space.

The $(1 + i)$-th line ($1 \le i \le K$) contains $2$ integers $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$) separated by a space. This means that the pasta on day $A_i$ has already been decided: when $B_i = 1$ it is tomato sauce, when $B_i = 2$ it is cream sauce, and when $B_i = 3$ it is basil sauce. All $A_i$ ($1 \le i \le K$) are distinct. In the given input data, it is guaranteed that there is at least $1$ schedule satisfying the conditions.

Output

Output the remainder when the number of schedules satisfying the conditions is divided by $10000$, in a single line.

Sample Input and Output

Sample Input 1

5 3
3 1
1 1
4 2

Sample Output 1

6

In Sample $1$, you consider a schedule for $5$ days. Day $1$ and day $3$ are tomato sauce, and day $4$ is cream sauce. Also, you must not choose the same pasta for $3$ or more consecutive days. There are $6$ schedules that satisfy these conditions.

In this table, $1$ represents tomato sauce, $2$ represents cream sauce, and $3$ represents basil sauce.

Sample Input 2

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

Sample Output 2

2640

In Sample $2$, there are $4112640$ schedules in total that satisfy the conditions. Output $2640$, which is the remainder when divided by $10000$.