#include<cstdio>
int n, p[128];
int memo[128][8][8];
int solve(int d, int p1, int p2){
  if(memo[d][p1][p2]) return memo[d][p1][p2];
  if(p[d] == p1 && p1 == p2) return memo[d][p1][p2] = 0;
  if(d == n + 1) return memo[d][p1][p2] = 1;
  if(p[d]) return memo[d][p1][p2] = solve(d + 1, p[d], p1);
  int ret = 0;
  if(!(p1 == p2 && p1 == 1))
    ret += solve(d + 1, 1, p1);
  if(!(p1 == p2 && p1 == 2))
    ret += solve(d + 1, 2, p1);
  if(!(p1 == p2 && p1 == 3))
    ret += solve(d + 1, 3, p1);
  return memo[d][p1][p2] = ret % 10000;
}
int main(void){
  int k, a, b;
  scanf("%d %d", &n, &k);
  for(int i = 0;i < k; i++){
    scanf("%d %d", &a, &b);
    p[a] = b;
  }
  printf("%d\n", solve(1, 5, 5));
}
