당신은 파스타를 매우 좋아해서 매일 저녁 식사로 파스타를 만들어 먹습니다. 당신은 토마토 소스, 크림 소스, 바질 소스의 $3$종류의 파스타를 만들 수 있습니다.

$N$일 동안의 저녁 식사 계획을 세우기로 했습니다. 매일 $3$종류의 파스타 중에서 $1$종류를 고릅니다. 단, 같은 파스타가 계속되면 질리기 때문에 $3$일 이상 연속해서 같은 파스타를 골라서는 안 됩니다. 또한, $N$일 중 $K$일치의 파스타는 이미 정해져 있습니다.

입력으로 $N$의 값과 $K$일치의 파스타 정보가 주어졌을 때, 조건을 만족하는 계획이 몇 가지인지 $10000$으로 나눈 나머지를 구하는 프로그램을 작성하십시오.

입력

입력은 $K + 1$줄로 이루어집니다.

$1$번째 줄에는 $2$개의 정수 $N, K$ ($3 \le N \le 100$, $1 \le K \le N$)가 공백으로 구분되어 적혀 있습니다.

$(1 + i)$번째 줄 ($1 \le i \le K$)에는 $2$개의 정수 $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$)가 공백으로 구분되어 적혀 있습니다. 이는 $A_i$일째의 파스타가 이미 정해져 있으며, $B_i = 1$일 때는 토마토 소스이고, $B_i = 2$일 때는 크림 소스이고, $B_i = 3$일 때는 바질 소스임을 나타냅니다. $A_i$ ($1 \le i \le K$)는 모두 다릅니다. 주어지는 입력 데이터에서 조건을 만족하는 계획이 $1$가지 이상 존재함이 보장됩니다.

출력

조건을 만족하는 계획의 가짓수를 $10000$으로 나눈 나머지를 한 줄에 출력하십시오.

입출력 예

입력 예 1

5 3
3 1
1 1
4 2

출력 예 1

6

입출력 예 $1$에서 당신은 $5$일간의 계획을 세웁니다. $1$일째와 $3$일째는 토마토 소스이고, $4$일째는 크림 소스입니다. 또한 $3$일 이상 연속해서 같은 파스타를 골라서는 안 됩니다. 이 조건들을 만족하는 계획은 $6$가지입니다.

이 표에서 $1$은 토마토 소스를, $2$는 크림 소스를, $3$은 바질 소스를 나타냅니다.

입력 예 2

20 5
10 2
4 3
12 1
13 2
9 1

출력 예 2

2640

입출력 예 $2$에서 조건을 만족하는 계획은 총 $4112640$가지입니다. 이를 $10000$으로 나눈 나머지인 $2640$을 출력합니다.