JOI logo
第11回日本情報オリンピック 予選4

2011年12月18日
情報オリンピック日本委員会

問題
   パスタ (Pasta)

問題

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

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

入力として N の値と,K 日分のパスタの情報が与えられたとき,条件をみたす予定が何通りあるかを 10000 で割った余りを求めるプログラムを作成せよ.

入力

入力は K + 1 行からなる.

1 行目には 2 つの整数 N, K (3 ≦ N ≦ 100,1 ≦ K ≦ N) が空白を区切りとして書かれている.

1 + i 行目 (1 ≦ i ≦ K) には 2 つの整数 Ai, Bi (1 ≦ Ai ≦ N,1 ≦ Bi ≦ 3) が空白を区切りとして書かれている.これは,Ai 日目のパスタはすでに決まっており,Bi = 1 のときはトマトソースであり,Bi = 2 のときはクリームソースであり,Bi = 3 のときはバジルソースであることを表す.Ai (1 ≦ i ≦ K) は全て異なる.与えられる入力データにおいて,条件をみたす予定は 1 通り以上あることが保証されている.

出力

条件をみたす予定が何通りあるかを 10000 で割った余りを 1 行で出力せよ.

入出力例

入力例 1 入力例 2
5 3
3 1
1 1
4 2
  
20 5
10 2
4 3
12 1
13 2
9 1
  
 
出力例 1 出力例 2
6
   
2640
   

入出力例 1 において,あなたは 5 日間の予定を考える.1 日目と 3 日目はトマトソースであり,4 日目はクリームソースである.また,3 日以上連続して同じパスタを選んではいけない.これらの条件をみたす予定は 6 通りある.
 1日目   2日目   3日目   4日目   5日目 
予定 1    1 2 1 2 1
予定 2    1 2 1 2 2
予定 3    1 2 1 2 3
予定 4    1 3 1 2 1
予定 5    1 3 1 2 2
予定 6    1 3 1 2 3
この表では,1 はトマトソースを,2 はクリームソースを,3 はバジルソースを表す.

入出力例 2 において,条件をみたす予定は全部で 4112640 通りある.それを 10000 で割った余りである 2640 を出力する.

※各入出力例のデータは, 右クリック等によりファイルに保存して利用可能です.


採点用データ

入力データ 入力1 入力2 入力3 入力4 入力5