require 'matrix'

class Array
	def accum
		inject([0]){|a, x| a + [a[-1] + x]}
	end

	def accum!
		(1..size-1).each{|i|
			self[i] += self[i-1]
		}
		self.unshift(0)
	end

	def accum_2d
		ac = map{|r| r.accum}
		(1..size-1).each{|i|
			(1..ac[0].size-1).each{|j|
				ac[i][j] += ac[i-1][j]
			}
		}
		ac.unshift([0] * ac[0].size)
		ac
	end

	def accum_2d!
		each{|r| r.accum!}
		(1..size-1).each{|i|
			(1..self[0].size-1).each{|j|
				self[i][j] += self[i-1][j]
			}
		}
		unshift([0] * self[0].size)
	end
		
	def bsearch_first_index(l = 0, r = size - 1, &pred)
		return nil if l > r
		c = (l + r) / 2 
		if pred[self[c]]
			bsearch_first_index(l, c-1, &pred) || c
		else
			bsearch_first_index(c+1, r, &pred)
		end
	end

	def bsearch_first_item(l = 0, r = size - 1, &pred)
		i = bsearch_first_index(l, r, &pred)
		i ? self[i] : nil
	end

	def bsearch_last_index(l = 0, r = size - 1, &pred)
		return nil if l > r
		c = (l + r) / 2 
		if pred[self[c]]
			bsearch_last_index(c+1, r, &pred) || c
		else
			bsearch_last_index(l, c-1, &pred)
		end
	end

	def bsearch_last_item(l = 0, r = size - 1, &pred)
		i = bsearch_last_index(l, r, &pred)
		i ? self[i] : nil
	end
end

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

start = Time.new
loop.with_index {|_, itr|
	#break if itr > 20
	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 = []
	memo = []
	
	prev_y = 1
	until obs.empty?
		x, y = obs.shift
		if y - prev_y > 1
			k = y - prev_y
		#	l, m = memo.bsearch_last_item{|l, m| l <= k-1}
		#	if l
		#		mats << m * exp(a, k-1-l, MOD)
		#	else
		#		mats << exp(a, k-1, MOD)
		#	end
		#	memo << [k-1, mats[-1]]
		#	memo.sort_by(&:first)
			mats << k-1
		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 << h-prev_y
	end

	v = [0] * w
	v[0] = 1
	
	t = mats.count{|x| x.class != Matrix}
	last_m = 1
	last_k = 0
	t.times {
		i = (0..mats.size-1).min_by{|i| mats[i].class == Matrix ? h : mats[i]}
		k = mats[i]
		mats[i] = exp(a, k-last_k, MOD) * last_m
		last_m = mats[i]
		last_k = k
	}
	#p mats
	
	v = Matrix[v]
	until mats.empty?
		v = v * mats.shift % MOD
	end
	c = v.to_a[0][-1]
	puts "Case #{itr+1}: #{c}"
}