파스타

상근이는 매일 저녁으로 파스타를 만들어 먹는다. 만들 수 있는 파스타는 토마토 소스, 크림 소스, 바질 소스 세 종류이다.

상근이는 앞으로 $N$일 동안 먹을 파스타를 계획하려고 한다. 매일 세 종류 중 하나를 고르는데, 같은 파스타를 계속 먹으면 질리기 때문에 같은 종류를 3일 이상 연속으로 먹지는 않는다. 즉, 어떤 파스타든 최대 2일까지만 연달아 먹을 수 있다.

또한 $N$일 중 $K$일은 먹을 파스타가 미리 정해져 있다.

$N$과 미리 정해진 날의 정보가 주어질 때, 가능한 계획의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 두 정수 $N$과 $K$가 주어진다. ($3 \le N \le 100$, $1 \le K \le N$)

다음 $K$개 줄에는 파스타가 미리 정해진 날의 정보가 한 줄에 하나씩 $A_i\ B_i$ 형식으로 주어진다. 이는 $A_i$일에 먹을 파스타가 $B_i$라는 뜻이다. $B_i$가 $1$이면 토마토 소스, $2$이면 크림 소스, $3$이면 바질 소스를 나타낸다. 모든 $A_i$는 서로 다르다.

가능한 계획의 수를 $10000$으로 나눈 나머지를 출력한다.

$N = 5$이고 1일에 토마토, 3일에 토마토, 4일에 크림 소스가 정해진 경우, 다음과 같이 총 6가지 계획이 가능하다. (각 숫자는 해당 날의 파스타 종류를 뜻한다.)

• 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