Problem Description

You love pasta so much that you make and eat pasta for dinner every day. You can make three types of pasta: tomato sauce, cream sauce, and basil sauce.

You have decided to plan your dinners for the next $N$ days. Each day, you can choose one of the three types of pasta. However, eating the same pasta for more than two consecutive days will get boring, so you cannot choose the same pasta for more than two consecutive days. Additionally, you have already decided on the pasta for $K$ days out of the $N$ days.

Given the values of $N$ and the information about the $K$ days' pasta, create a program that calculates the number of possible schedules that satisfy these conditions, modulo $10,000$.

Input Format

The input consists of $K + 1$ lines.

The first line contains two integers $N$ and $K$ ($3 \leq N \leq 100$, $1 \leq K \leq N$), separated by a space.

The $(1 + i)$-th line ($1 \leq i \leq K$) contains two integers $A_i$ and $B_i$ ($1 \leq A_i \leq N$, $1 \leq B_i \leq 3$), separated by a space. This indicates that the pasta for the $A_i$-th day has already been decided, where $B_i = 1$ means tomato sauce, $B_i = 2$ means cream sauce, and $B_i = 3$ means basil sauce. All $A_i$ ($1 \leq i \leq K$) are distinct. It is guaranteed that there is at least one possible schedule that satisfies the conditions in the given input data.

Output Format

Output the number of possible schedules that satisfy the conditions, modulo $10,000$, on a single line.

Sample Input and Output

Sample Input #1

5 3
3 1
1 1
4 2

Sample Output #1

6

Sample Input #2

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

Sample Output #2

2640

Notes/Hints

Sample Explanation 1

In the first sample input/output, you are planning for 5 days. Days 1 and 3 are tomato sauce, and day 4 is cream sauce. You cannot choose the same pasta for more than two consecutive days. There are 6 possible schedules that satisfy these conditions. In this table, 1 represents tomato sauce, 2 represents cream sauce, and 3 represents basil sauce.

Sample Explanation 2

In the second sample input/output, there are a total of 4,112,640 possible schedules that satisfy the conditions. Output the remainder when this number is divided by 10,000, which is 2,640.

见题面 Input 部分

见题面 Output 部分