=begin
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0568
dp[i][j][k]:i??\???????????????k??\???????????????j
????????\????????????????±??????£???????????¨???
  <=> h[i] != -1, j = h[i]
  ??¬??\???1??\???????????????j dp[i][j][1]
    = i-1??\???????????????j?????????1,2??\???????????????
    = dp[i-1][j_][k_] sum for j_:x!=j, k_:[1,2]
  ??¬??\???2??\???????????????j dp[i][j][2]
    = i-1??\???????????????1??\???????????????j
????????\????????????????±??????£??????????????¨???
  ?±??????£???????????¨?????????????????????????????±????????????????????????
    <=> j = 0, 1, 2
=end

def mod n, i, m=3
  (n + i) % m
end

MOD = 10000
n, k = gets.split.map(&:to_i)

h = Hash.new(-1)
k.times{ 
  a, b = gets.split.map{|x| x.to_i.pred}
  h[a] = b
}

dp = Array.new(n.succ).map{Array.new(3).map{Array.new(3, 0)}}
3.times { |j|
  dp[0][j][1] = 1 if h[0] == -1 || h[0] == j
}

n.pred.times { |i|
  3.times { |j|
    b = h[i.succ] == -1 || h[i.succ] == j
    for j_ in (1..2)
      for k in (1..2)
        dp[i.succ][j][1] += dp[i][mod(j, j_)][k] % MOD if b
      end     
    end     
    dp[i.succ][j][2] += dp[i][j][1] % MOD if b
  }
}
p dp[n.pred].map{|arr| arr.inject :+}.inject(:+) % MOD