{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\n\u003cp\u003e\nThere is a grid that consists of \u003cvar\u003eW \\times H\u003c/var\u003e cells. The upper-left-most cell is \u003cvar\u003e(1, 1)\u003c/var\u003e.\nYou are standing on the cell of \u003cvar\u003e(1,1)\u003c/var\u003e and you are going to move to cell of \u003cvar\u003e(W, H)\u003c/var\u003e.\nYou can only move to adjacent lower-left, lower or lower-right cells.\n\u003c/p\u003e\n\n\u003cp\u003e\nThere are obstructions on several cells. You can not move to it. You cannot move out the grid, either.\nWrite a program that outputs the number of ways to reach \u003cvar\u003e(W,H)\u003c/var\u003e modulo 1,000,000,009.\nYou can assume that there is no obstruction at \u003cvar\u003e(1,1)\u003c/var\u003e.\n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cp\u003e\nThe first line contains three integers, the width \u003cvar\u003eW\u003c/var\u003e, the height \u003cvar\u003eH\u003c/var\u003e, and the number of obstructions \u003cvar\u003eN\u003c/var\u003e. \n(\u003cvar\u003e1 \\leq W \\leq 75\u003c/var\u003e, \u003cvar\u003e2 \\leq H \\leq 10^{18}\u003c/var\u003e, \u003cvar\u003e0 \\leq N \\leq 30\u003c/var\u003e)\nEach of following \u003cvar\u003eN\u003c/var\u003e lines contains 2 integers, denoting the position of an obstruction \u003cvar\u003e(x_i, y_i)\u003c/var\u003e.\n\u003c/p\u003e\n\n\u003cp\u003e\nThe last test case is followed by a line containing three zeros.\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\nFor each test case, print its case number and the number of ways to reach \u003cvar\u003e(W,H)\u003c/var\u003e modulo 1,000,000,009.\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input\u003c/h2\u003e\n\n\u003cpre\u003e2 4 1\n2 1\n2 2 1\n2 2\n0 0 0\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input\u003c/h2\u003e\n\n\u003cpre\u003eCase 1: 4\nCase 2: 0\n\u003c/pre\u003e\n"}}]}