문제
세계의 다양한 요리를 직접 만들어 먹어보는 것을 즐기는 유리가 요즘에는 파스타에 푹 빠졌다.
그래서 매일 저녁 메뉴로 파스타를 만들어 먹는다.
유리가 만들 수 있는 파스타는 세 종류로서 토마토 파스타, 크림 파스타, 미트볼 파스타이다.
유리는 친구들을 초대하여 파스타를 함께 먹기도 하는데 이러한 약속을 포함하여 N일 간의 식단을 짤 생각이다.
같은 종류의 파스타를 매일 먹으면 질릴 수 있으므로 같은 종류의 파스타를 3일 이상 연속하여 먹지 않도록 식단을 짤 생각이다.
또한 K개의 약속한 날에는 정해진 파스타를 만들 생각이다.
N일 동안의 식단을 계획하는 방법은 몇 가지나 될까?
유리와 함께 프로그램을 작성하여 구해보자.
입력 예 1을 예로 보자.
유리는 5일간의 식단을 계획하고 있다. 3개의 약속이 있어서 1일째와 3일째는 토마토 파스타, 4일째는 크림파스타로 정해놓고 생각할 것이다.
편의상 토마토 파스타를 1번, 크림 파스타를 2번, 미트볼 파스타를 3번으로 한다.
입력
첫 행에 날짜수 N, 약속한 날짜 수 K( 3 <= N <= 100, 1 <= K <= N)이 공백으로 구분하여 입력된다.
이어서 K개의 행에 Ai, Bi(1 <= Ai <=N, 1 <= Bi <= 3)가 공백으로 구분하여 입력된다.
Ai일에 정해진 파스타는 Bi라는 의미로 Bi가 1인 경우 토마토, 2인 경우 크림, 3인 경우 미트볼 파스타이다.
Ai는 모두 서로 다른 수이고 모든 조건을 충족하는 가지 수가 적어도 1가지 이상 있도록 입력된다.
출력
유리가 식단을 계획할 수 있는 경우의 수를 구하여 10000으로 나눈 나머지를 출력한다.
예제1
입력
53
31
11
42
출력
6
예제2
입력
205
102
43
121
132
91
출력
2640
출처
JOI 2011/2012 예선 4