#include <iostream>
#include <cstring>
#define MOD 10000
using namespace std;

int n,k,m[101];
int dp[4][4][4][101];

int rec(int a,int b,int c,int idx){
  if(m[idx] != -1 && m[idx] != c) return 0;
  if(a == b && b == c) return 0;
  if(idx == n) return 1;
  if(dp[a][b][c][idx] != 0) return dp[a][b][c][idx];
  return dp[a][b][c][idx] = (rec(b,c,1,idx+1) + rec(b,c,2,idx+1) + rec(b,c,3,idx+1))%MOD;
}

int main(){
  cin >> n >> k;
  memset(m,-1,sizeof(m));
  while(k--){
    int d,s; cin >> d >> s; 
    m[d] = s;
  }
  cout << (rec(0,0,1,1) + rec(0,0,2,1) + rec(0,0,3,1))%MOD << endl;
}