파스타

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

상근이는 앞으로 N일 동안 먹을 파스타를 계획하려고 한다. 매일 매일 세 종류의 파스타 중 한 종류를 선택할 것이다. 하지만, 같은 파스타를 계속해서 먹으면 질려버릴 수 있기 때문에, 3일 이상 연속해서 같은 파스타를 먹지 않는다.

또, N일 중 K일에 먹을 파스타는 미리 정해두었다.

N과 K일에 먹을 파스타가 주어졌을 때, 가능한 계획의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 100, 1 ≤ K ≤ N)

둘째 줄부터 K개 줄에는, 미리 파스타를 정해놓은 날의 정보가 주어진다. 이 정보는 Ai Bi와 같은 형식이며, Ai일에 먹을 파스타는 Bi라는 뜻이다. 이때, Bi = 1이면 토마토 소스, 2이면 크림 소스, 3이면 바질 소스이다. Ai는 모두 다르다.

상근이가 세울 수 있는 계획의 수를 10000으로 나눈 나머지를 출력한다.

예제 1의 경우에는 총 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