세 갈래 이동

가로 $W$칸, 세로 $H$칸인 격자가 있다. 가장 왼쪽 위 칸이 $(1, 1)$이고, 오른쪽으로 갈수록 첫 번째 좌표가 커지고 아래로 갈수록 두 번째 좌표가 커진다. 지금 $(1, 1)$에 서 있고 $(W, H)$까지 가려고 한다.

칸 $(x, y)$에서는 바로 아래 왼쪽 칸 $(x - 1, y + 1)$, 바로 아래 칸 $(x, y + 1)$, 바로 아래 오른쪽 칸 $(x + 1, y + 1)$ 중 한 칸으로만 이동할 수 있다.

몇몇 칸에는 장애물이 있다. 장애물이 있는 칸으로는 이동할 수 없고, 격자 밖으로 나갈 수도 없다. $(W, H)$에 도달하는 경로의 수를 1,000,000,009로 나눈 나머지를 구하는 프로그램을 작성하라. $(1, 1)$에는 장애물이 없다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에 격자의 가로 길이 $W$, 세로 길이 $H$, 장애물의 개수 $N$이 공백을 사이에 두고 주어진다. ($1 \le W \le 75$, $2 \le H \le 10^{18}$, $0 \le N \le 30$)

이어지는 $N$개의 줄에 장애물의 위치 $x_i$, $y_i$가 주어진다. ($1 \le x_i \le W$, $1 \le y_i \le H$)

마지막 테스트 케이스 다음 줄에는 $0$이 세 개 주어진다.

각 테스트 케이스마다 케이스 번호와 $(W, H)$에 도달하는 경로의 수를 1,000,000,009로 나눈 나머지를 한 줄에 출력한다. $k$번째 테스트 케이스의 답이 $a$이면 Case k: a 형식으로 출력한다.