Pasta

Interview

Time limit1sMemory limit128 MB

Summary

Count sequences of length N over three kinds where no kind appears three or more times in a row, with some positions fixed, modulo 10000.

Level: Medium4 of 10
Topics: Dynamic programming, Implementation
Solved: No attempts yet

Problem

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.

Input

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.

Output

Print the number of possible plans modulo $10000$ .

Hint

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

Examples2

Example 1
Input
```
5 3
3 1
1 1
4 2
```
Expected output
```
6
```
Example 2
Input
```
20 5
10 2
4 3
12 1
13 2
9 1
```
Expected output
```
2640
```