#include <bits/stdc++.h>
using namespace std;
#define Rep(i,N) for(int i = 0; i < N; i++)
#define INF 1 << 28
#define S second
#define F first
typedef pair<int,int> Pi;

inline void chmax(int &a, int b) { a = max(a,b); }
inline void chmin(int &a, int b) { a = min(a,b); }


int N, K;
int data[105];
int memo[105][4][2];

int dfs(int it, int ch, int cnt)
{
  int ret = 0;
  if(it == N)return 1;
  if(~memo[it][ch][cnt])return memo[it][ch][cnt];
  Rep(i,3) {
    if(data[it + 1] != INF && i != data[it + 1])continue;
    int nc;
    if(ch == i) nc = cnt + 1;
    else nc = 0;
    if(nc < 2) (ret += dfs(it + 1,i,nc)) %= 10000;
  }
  return memo[it][ch][cnt] = ret;
}

int main()
{
  memset(memo,-1,sizeof(memo));
  cin >> N >> K;
  int A, B;
  fill(data,data + 105,INF);
  Rep(i,K) {
    cin >> A >> B; --B;
    data[A] = B;
  }
  cout << dfs(0,3,0) << endl;
  return(0);
}
  