#include<stdio.h>
int dp[101][4][4];
int main(void)
{
	int n,d;
	int a,b;
	int pa[101];
	int s=0;
	int i,j,k,l;
	
	scanf("%d %d",&n,&d);
	for(i=1;i<=n;i++){
		pa[i]=0;
		for(j=1;j<=3;j++){
			for(k=1;k<=3;k++){
				dp[i][j][k]=0;
			}
		}
	}
	for(i=1;i<=d;i++){
		scanf("%d %d",&a,&b);
		pa[a]=b;
	}
	if(pa[1]==0){
		for(i=1;i<=3;i++){
			dp[1][i][1]=1;
		}
	}
	else {
		dp[1][pa[1]][1]=1;
	}
	for(i=1;i<=3;i++){
		if(pa[1]==i || pa[1]==0){
			for(j=1;j<=3;j++){
				if(pa[2]==j || pa[2]==0){
					dp[2][j][i]+=1;
				}
			}
		}
	}
	for(i=2;i<n;i++){
		for(j=1;j<=3;j++){
			if(pa[i]==j || pa[i]==0){
				for(k=1;k<=3;k++){
					for(l=1;l<=3;l++){
						if(pa[i+1]==l || pa[i+1]==0){
							if(!(j==k && l==j)){
								dp[i+1][l][j]+=dp[i][j][k];
								dp[i+1][l][j]=dp[i+1][l][j]%10000;
							}
						}
					}
				}
			}
		}
	}
	
/*	for(i=1;i<=n;i++){
		for(j=1;j<=3;j++){
			for(k=1;k<=3;k++){
				printf(" %d",dp[i][j][k]);
			}
			printf(" |");
		}
		printf("\n");
	}*/
	for(i=1;i<=3;i++){
		for(j=1;j<=3;j++){
			s+=dp[n][i][j];
			s=s%10000;
		}
	}
	printf("%d\n",s);
	return 0;
}