#! ruby -Ks

n, k = gets.strip.split(' ').map{|s| s.to_i}
d = Array.new(n,-1)
k.times do |i|
	a, b = gets.strip.split(' ').map{|s| s.to_i}
	d[a - 1] = b - 1;
end
dp = Array.new(2){Array.new(3,0)}
3.times do |i|
	3.times do |j|
		if (d[0] < 0 || d[0] == i) && (d[1] < 0 || d[1] == j)
			if i == j
				dp[0][j] += 1
			else
				dp[1][j] += 1
			end
		end
	end
end
for i in 2...n
	dpw = Array.new(2){Array.new(3,0)}
	3.times do |j|
		if d[i] < 0 || d[i] == j
			3.times do |k|
				if j == k
					dpw[0][j] += dp[1][k]
				else
					dpw[1][j] += dp[0][k] + dp[1][k]
				end
			end
		end
	end
	3.times do |j|
		dp[0][j] = dpw[0][j] % 10000
		dp[1][j] = dpw[1][j] % 10000
	end
end
all = 0
3.times do |i|
	all += dp[0][i] + dp[1][i]
end
print(all % 10000,"\n")