あなたはパスタが大好物であり，毎日，晩御飯にパスタを作って食べている．あなたはトマトソース，クリームソース，バジルソースの $3$ 種類のパスタを作ることができる．

$N$ 日間の晩御飯の予定を考えることにした．それぞれの日に $3$ 種類のパスタから $1$ 種類を選ぶ．ただし，同じパスタが続くと飽きてしまうので，$3$ 日以上連続して同じパスタを選んではいけない．また，$N$ 日のうちの $K$ 日分のパスタはすでに決めてある．

入力として $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$ を出力する．