레이팅 미적용설명
あなたはパスタが大好物であり,毎日,晩御飯にパスタを作って食べている.あなたはトマトソース,クリームソース,バジルソースの 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 つの整数 A i , B i (1 ≦ A i ≦ N,1 ≦ B i ≦ 3) が空白を区切りとして書かれている.これは,A i 日目のパスタはすでに決まっており,B i = 1 のときはトマトソースであり,B i = 2 のときはクリームソースであり,B i = 3 のときはバジルソースであることを表す.A i (1 ≦ i ≦ K) は全て異なる.与えられる入力データにおいて,条件をみたす予定は 1 通り以上あることが保証されている.
출력 형식
条件をみたす予定が何通りあるかを 10000 で割った余りを 1 行で出力せよ.
예제 1
입력
5 3
3 1
1 1
4 2출력
6문제 정보