#include <iostream>
#include <algorithm>
using namespace std;

const int mod = 10000;
int N, K;
int B[102];

int main() {
  cin >> N >> K;
  fill(B,B+N,-1);
  for(int i = 0; i < K; ++i) {
    int A;
    cin >> A;
    cin >> B[A-1];
    --B[A-1];
  }

  int T[102][3][3];
  fill(T[0][0],T[102][0],0);
  if(B[0] == -1) 
    T[0][0][1] = T[0][1][1] = T[0][2][1] = 1;
  else
    T[0][B[0]][1] = 1;

  for(int i = 1; i < N; ++i) {
    for(int a = 0; a < 3; ++a) {
      for(int b = 0; b < 3; ++b) {
	for(int c = 0, d = 1; c < 3 && d; ++c) {
	  if(B[i] != -1) {
	    c = B[i];
	    d = 0;
	  }
	  int nb;
	  if(a == c) nb = b+1;
	  else nb = 1;
	  if(nb >= 3) continue;
	  T[i][c][nb] = (T[i][c][nb] + T[i-1][a][b]) % mod;
	}
      }
    }
  }
  int sum = 0;
  for(int i = 0; i < 3; ++i) {
    for(int j = 0; j < 3; ++j) {
      sum = (sum+T[N-1][i][j])%mod;
    }
  }
  cout << sum << endl;
  return 0;
}