#include<bits/stdc++.h>
using namespace std;
int dfs(int day,int tmt,int cream,int bazil);
int dfsmem[105][3][3][3];
int n,k;
int mem[105];
int main(){
  cin>>n>>k;
  memset(mem,-1,sizeof(mem));
  memset(dfsmem,-1,sizeof(dfsmem));
  for(int i=0;i<k;i++){
    int a,b;
    cin>>a>>b;
    mem[a]=b;
  }
  cout<<dfs(1,0,0,0)<<endl;
}
int dfs(int day,int tmt,int cream,int bazil){
  if(tmt>=3||cream>=3||bazil>=3){
    return 0;
  }
  else if(day>n){
    return 1;
  }
  else if(dfsmem[day][tmt][cream][bazil]!=-1){
    return dfsmem[day][tmt][cream][bazil];
  }
  else if(mem[day]!=-1){
    if(mem[day]==1){
      return dfsmem[day][tmt][cream][bazil]=dfs(day+1,tmt+1,0,0)%10000;
    }
    else if(mem[day]==2){
      return dfsmem[day][tmt][cream][bazil]=dfs(day+1,0,cream+1,0)%10000;
    }
    else if(mem[day]==3){
      return dfsmem[day][tmt][cream][bazil]=dfs(day+1,0,0,bazil+1)%10000;
    }
  }
  else{
    int paturn=0;
    paturn+=dfs(day+1,tmt+1,0,0)%10000;
    paturn+=dfs(day+1,0,cream+1,0)%10000;
    paturn+=dfs(day+1,0,0,bazil+1)%10000;
    return dfsmem[day][tmt][cream][bazil]=paturn%10000;
  }
}