#include<iostream>
using namespace std;

int main(){
  int m[100];
  int n,k,a,b;

  cin >> n >> k;

  for(int i=0;i<n;i++)m[i] = -1;
  for(int i=0;i<k;i++){
    cin >> a >> b;
    m[a-1] = b-1;
  }

  int dp[101][3][3];
  for(int i=0;i<n;i++)
    for(int j=0;j<3;j++)
      for(int k=0;k<3;k++)dp[i][j][k] = 0;
  
  for(int i=0;i<n;i++){
    if(i==0){
      if(m[i]<0){
	for(int j=0;j<3;j++)dp[i][j][(j+1)%3] = 1;
      }else{
	dp[i][m[i]][(m[i]+1)%3] = 1;
      }
    }else{
      for(int j=0;j<3;j++){
	for(int k=0;k<3;k++){
	  if(m[i]<0){
	    for(int l=0;l<3;l++){
	      if(l==k && k==j)continue;
	      else {
	      dp[i][l][j] += dp[i-1][j][k]; 
	      dp[i][l][j] %= 10000;
	      }
	    }
	  }else{
	    if(!(j==m[i] && k==m[i]) ){
	      dp[i][m[i]][j] += dp[i-1][j][k];
	      dp[i][m[i]][j] %= 10000;
	    }
	  }
	}
      }
    }
  }
  /*
  for(int i=0;i<n;i++){
    for(int j=0;j<3;j++)for(int k=0;k<3;k++)cout << dp[i][j][k] << " ";
    cout << endl;
  }
  */
  int ans = 0;
  for(int i=0;i<3;i++)
    for(int j=0;j<3;j++){
      ans += dp[n-1][i][j];
      ans %= 10000;
    }

  cout << ans << endl;
}