module Memoizable
	def memoize(name)
		original = "__original_#{name}__"
		([Class, Module].include?(self.class) ? self : self.class).class_eval {
			alias_method(original, name)
			private(original)
			cache = {}
			define_method(name){|*args|
				cache[args] ||= send(original, *args)
			}
		}
	end 
end

def f(schedule, n)  
	x = (schedule & 0b11)
	y = ((schedule & 0b1100) >> 2)
	z = ((schedule & 0b110000) >> 4)
	return (f(schedule | 1, n) + f(schedule | 2, n) + f(schedule | 3, n)) % 10000 if x == 0
	return (f(schedule | 4, n) + f(schedule | 8, n) + f(schedule | 12, n)) % 10000 if y == 0
	return (f(schedule | 16, n) + f(schedule | 32, n) + f(schedule | 48, n)) % 10000 if z == 0
	return 0 if x == y && y == z
	return 1 if n == 3
	f(schedule >> 2, n - 1) % 10000
end

include Memoizable
memoize :f

n, k = gets.split.map(&:to_i)
schedule = 0
k.times {
	a, b = gets.split.map(&:to_i)
	schedule |= (b << 2 * (a-1))
}
p f(schedule, n)