require 'matrix'

class Matrix
	def []=(i, j, x)
		@rows[i][j] = x	
	end

	def %(mod)
		map{|x| x % mod}
	end
end

def exp(n, k, mod = nil)
	x = 1	
	r = n
	while k > 0
		x *= r if k & 1 == 1
		r *= r		
		if mod
			x %= mod
			r %= mod
		end
		k >>= 1
	end
	x
end

MOD = 1_000_000_009

loop.with_index {|_, itr|
	w, h, n = gets.split.map &:to_i
	break if w == 0
	obs = (1..n).map{ gets.split.map &:to_i }
	obs.sort_by!(&:last)
	obs.shift while obs[0] && obs[0][1] == 1

	a = Matrix.build(w, w){|i, j|
		(0 <= j && j < w && i-1 <= j && j <= i+1) ? 1 : 0
	}

	mats = []
	
	prev_y = 1
	until obs.empty?
		x, y = obs.shift
		if y - prev_y > 1
			mats << exp(a, y-prev_y-1, MOD)
		end

		xs = [x]
		while obs[0] && obs[0][1] == y
			xs << obs.shift[0]
		end
		b = Marshal.load(Marshal.dump(a))
		xs.each{|x|
			b[x-2, x-1] = 0 if x-2 >= 0
			b[x-1, x-1] = 0
			b[x, x-1] = 0 if x <= w-1 
		}
		mats << b
		
		prev_y = y
	end	

	if prev_y < h
		mats << exp(a, h-prev_y, MOD)
	end

	v = [0] * w
	v[0] = 1
	c = (Matrix[v] * mats.inject(:+))[0, -1]
	puts "Case #{itr+1}: #{c}"
}