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)}}
if h[0] != -1
  dp[0][h[0]][1] = 1
else
  3.times { |j|
    dp[0][j][1] = 1
  }
end

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