#include<cstdio>
#include<cstring>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int n,fixed[100];

int dp[100][4][3];
int dfs(int i,int pre,int con){ // 今何日目か, 前日のパスタ, pre が何回連続したか
	if(con==3) return 0;
	if(i==n) return 1;

	if(dp[i][pre][con]!=-1) return dp[i][pre][con];

	int res=0;
	if(fixed[i]==0){
		for(int j=1;j<=3;j++){
			res+=dfs(i+1,j,pre==j?con+1:1);
		}
	}
	else{
		res=dfs(i+1,fixed[i],pre==fixed[i]?con+1:1);
	}
	return dp[i][pre][con]=res%10000;
}

int main(){
	int k; scanf("%d%d",&n,&k);
	rep(i,k){
		int a,b; scanf("%d%d",&a,&b); a--;
		fixed[a]=b;
	}

	memset(dp,-1,sizeof dp);
	printf("%d\n",dfs(0,0,0));

	return 0;
}