#include<iostream>
#include<cstring>
#include<vector>

using namespace std;

int solve(int,int,int);

int n,k,cnt;
int d[102];
int memo[102][4][4];

int main(){
	cin >> n >> k;
	
	for(int i=0;i<k;i++){
		int tmp;
		cin >> tmp;
		cin >> d[tmp];
	}
	cout << solve(1,0,0) << endl;
	return 0;
}

int solve(int day,int old_type,int type){
	int rec = 0;
	if(memo[day][old_type][type] != 0)return memo[day][old_type][type];
	
	if(day == n+1){
		rec = 1;
	}
	else if(d[day] != 0){
		if(old_type == type && type == d[day])rec = 0;
		else rec = solve(day+1,type,d[day]);
	}
	else{
		for(int i=1;i<=3;i++){
			if(old_type == type && type == i)continue;
			rec += solve(day+1,type,i);
		}
	}
	return memo[day][old_type][type] = rec%10000;
}