#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int dp[100][2][3];

int main(){
	int n,k,a[100],b[100];
	scanf("%d%d",&n,&k);
	dp[0][0][0]=dp[0][0][1]=dp[0][0][2]=1;
	for(int i=0;i<k;i++){
		scanf("%d%d",&a[i],&b[i]);
		for(int j=0;j<3;j++) if(b[i]!=j+1) dp[a[i]-1][0][j]=dp[a[i]-1][1][j]=-1;
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<3;j++){
			if(dp[i][0][j]==-1) continue;
			for(int k=0;k<3;k++){
				if(k==j) dp[i][1][j]=(dp[i][1][j]+(dp[i-1][0][k]==-1?0:dp[i-1][0][k]))%10000;
				else dp[i][0][j]=(dp[i][0][j]+(dp[i-1][0][k]==-1?0:dp[i-1][0][k])+(dp[i-1][1][k]==-1?0:dp[i-1][1][k]))%10000;
			}
		}
	}
	int res=0;
	for(int i=0;i<3;i++) res+=(dp[n-1][0][i]==-1?0:dp[n-1][0][i])+(dp[n-1][1][i]==-1?0:dp[n-1][1][i]);
	res%=10000;
	printf("%d\n",res);
}