#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, k;
int a, b, plan[110];
int dp[110][10][10];
long long int solve(int i, int sum, int bef);
int main(){
  memset(plan, -1, sizeof(plan));
  memset(dp, -1, sizeof(dp));
  cin >> n >> k;
  for(int i = 0; i < k; i++){
    cin >> a >> b;
    plan[a] = b;
  }
  cout << solve(1, 0, 0) % 10000 << endl;
}

long long int solve(int i, int sum, int bef){
  if(sum == 2) return 0;
  if(dp[i][sum][bef] >= 0) return dp[i][sum][bef];
  if(i == n + 1){
    return 1;
  }
  if(plan[i] == -1){
    return dp[i][sum][bef] = solve(i + 1, bef == 1? sum + 1 : 0 , 1) + solve(i + 1, bef == 2? sum + 1 : 0, 2) + solve(i + 1, bef == 3? sum + 1 : 0, 3) % 10000;
  }
  else{
    return dp[i][sum][bef] = solve(i + 1, bef == plan[i]? sum + 1 : 0, plan[i]) % 10000;
  }
}