#include<iostream>
#include<map>
#include<cstring>
using namespace std;
#define NUM 10000
int hashs[102];
int N,K;
long long int dp[5][5][102];


long long int check(int i,int j,int k)
{
  //  cerr<<"#"<<i<<" "<<j<<" "<<k<<endl;

  long long int sum=0;
  if(k==N)
    return 1;
  if(dp[i][j][k]!=-1)
    return dp[i][j][k];

  for(int x=1;x<4;x++)
    {
      if(!(i==x && j==x) && (hashs[k+1]==-1 || hashs[k+1]==x))
        sum+=check(j,x,k+1)%NUM;
    }
  dp[i][j][k]=sum;
  return sum;

}



int main()
{
  memset(dp,-1,sizeof(dp));
    memset(hashs,-1,sizeof(hashs));

  cin>>N>>K;
  for(int i=0;i<K;i++)
    {
      int a,b;
      cin>>a>>b;

      hashs[a]=b;
    }
  long long int ans=check(0,0,0);
  cout<<ans%NUM<<endl;


}