#include <cstdio>
#include <cstring>

int n;
int dec[105]={};
int dp[105][4][4]={};

void modadd(int &p,int q){
	p=(p+q)%10000;
}

int rec(int d,int p1,int p2){
	if(dp[d][p1][p2]!=-1)return dp[d][p1][p2];
	int r=0;
	if(d==2){
		if((dec[d]!=0 && dec[d]!=p2) || (dec[d-1]!=0 && dec[d-1]!=p1))goto re;
		r=1;
		goto re;
	}
	else{
		if((dec[d]!=0 && dec[d]!=p2) || (dec[d-1]!=0 && dec[d-1]!=p1))goto re;
		for(int i=1;i<=3;i++){
			if( !(i==p1 && p1==p2) ) modadd(r,rec(d-1,i,p1));
		}
	}
re:;
	dp[d][p1][p2]=r;
	return r;
}

int main(void){
	memset(dp,-1,sizeof(dp));
	int k,a,b;
	scanf("%d%d", &n, &k);
	for(int i=0;i<k;i++){
		scanf("%d%d", &a, &b);
		dec[a]=b;
	}
	int r=0;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			modadd(r,rec(n,i,j));
		}
	}
	printf("%d\n",r);
	return 0;
}