Pasta

Sanggeun makes pasta for dinner every day. There are three kinds of pasta he can make: tomato sauce, cream sauce, and basil sauce.

He wants to plan the pasta he will eat over the next $N$ days. Each day he picks one of the three kinds, but because eating the same pasta too many days in a row gets tiring, he never eats the same kind on three or more consecutive days. In other words, any single kind may be eaten on at most two days in a row.

In addition, the pasta for $K$ of the $N$ days is fixed in advance.

Given $N$ and the fixed-day information, write a program that counts the number of possible plans.

The first line contains two integers $N$ and $K$. ($3 \le N \le 100$, $1 \le K \le N$)

Each of the next $K$ lines describes one fixed day in the form $A_i\ B_i$, meaning the pasta eaten on day $A_i$ is $B_i$. Here $B_i = 1$ means tomato sauce, $2$ means cream sauce, and $3$ means basil sauce. All $A_i$ are distinct.

Print the number of possible plans modulo $10000$.

When $N = 5$ and the pasta is fixed to tomato on day 1, tomato on day 3, and cream on day 4, the following 6 plans are possible. (Each number is the pasta kind eaten on that day.)

• 1, 2, 1, 2, 1
• 1, 2, 1, 2, 2
• 1, 2, 1, 2, 3
• 1, 3, 1, 2, 1
• 1, 3, 1, 2, 2
• 1, 3, 1, 2, 3