## constant

MOD = 10000

### subroutines

def count_rec(m, b0, b1)
  return 1 if m >= $n
  return $crcache[m][b0][b1] if ! $crcache[m][b0][b1].nil?

  count = 0

  for b in (0..2)
    if ($abs[m].nil? || $abs[m] == b) && (b != b0 || b != b1)
      count = (count + count_rec(m + 1, b1, b)) % MOD
    end
  end

  $crcache[m][b0][b1] = count
end

### main

$n, k = gets.strip.split(' ').map{|s| s.to_i}

$abs = []

k.times do
  ai, bi = gets.strip.split(' ').map{|s| s.to_i - 1}
  $abs[ai] = bi
end

$crcache = $n.times.map{3.times.map{[]}}

count = 0

for i in (0..2)
  next if ! $abs[0].nil? && $abs[0] != i

  for j in (0..2)
    next if ! $abs[1].nil? && $abs[1] != j

    count = (count + count_rec(2, i, j)) % MOD
  end
end

puts count