#include<stdio.h>
int main()
{
	int dp[101][3][3]={},N,K,A,B,i,j,k,l,a[101]={},MOD=10000;
	for(scanf("%d%d",&N,&K);K--;)
	{
		scanf("%d%d",&A,&B);
		a[A]=B;
	}
	if(a[1])dp[1][a[1]-1][1]=1;
	else for(i=0;i<3;++i)dp[1][i][1]=1;
	for(i=2;i<=N;++i)
	{
		if(a[i])
		{
			for(j=0;j<2;++j)for(k=0;k<3;++k)
			{
					int&r=dp[i][a[i]-1][1];
					r=(r+dp[i-1][(a[i]+j)%3][k])%MOD;
			}
			for(k=0;k<2;++k)
			{
				int&r=dp[i][a[i]-1][k+1];
				r=(r+dp[i-1][a[i]-1][k])%MOD;
			}
		}
		else
		{
			for(j=0;j<3;++j)for(k=0;k<3;++k)
			{
				if(k)
				{
					int&r=dp[i][j][k];
					r=(r+dp[i-1][j][k-1])%MOD;
				}
				int&r=dp[i][j][1];
				for(l=1;l<3;++l)r=(r+dp[i-1][(j+l)%3][k])%MOD;
			}
		}
	}
	int res=0;
	for(j=0;j<3;++j)for(k=0;k<3;++k)res+=dp[N][j][k];
	printf("%d\n",res%MOD);
	return 0;
}