#include <iostream>
#include <algorithm>
using namespace std;

int memo[101][4][4];
int N, K;
int A, B;
int plan[101];

int rec(int d, int y, int a){
	if(d == N + 1)return 1;
	if(memo[d][y][a] != -1)return memo[d][y][a];
	
	if(plan[d] != 0){
		if(a == y && y == plan[d]){
			return 0;
		}
		else {
			return rec(d + 1, plan[d], y) % 10000;
		}
	}
	
	int best = 0;
	for(int next = 1; next <= 3; next++){
		if(a == y && y == next){
			continue;
		}
		else{
			best += rec(d + 1, next, y) % 10000;
		}
	}
	
	return memo[d][y][a] = best % 10000;
}

int main() {
	for(int i = 0; i <= 100; i++)
		for(int j = 0; j < 4; j++)
			for(int k = 0; k < 4; k++)
				memo[i][j][k] = -1;
				
	cin >> N >> K;
	
	for(int i = 0; i < K; i++){
		cin >> A >> B;
		plan[A] = B;
	}
		
	
	cout << rec(1, 0, 0) << endl;
	
	return 0;
}